[Project Euler] Problem 007

#include <stdio.h>
 
int isPrime(int num);
 
int main()
{
    int i;
    int count = 1;
 
    for (i = 2; count <= 10001; i++)
    {
        if (isPrime(i)) { ++count; }
    }
 
    printf("answer: %d\n", i -= 1);
 
    return 0;
}
 
int isPrime(int num)
{
    int i;
 
    if (num != 2)
    {
        if (num % 2 == 0) { return 0; }
        else
        {
            for (i = 3; i*i <= num; i += 2)
            {
                if (num%i == 0) { return 0; }
            }
        }
    }
 
    return 1;
}
 

정답: 104743

에라토스테네스의 체보다 이 방법이 더 적절하다고 판단했다.

실행 시간을 더 줄이려면 다음도 생각할 수 있다.

#include <stdio.h>
 
int isPrime(int num);
 
int main()
{
    int i;
    int count = 2;
 
    for (i = 3; count <= 10001; i += 2)
    {
        if (isPrime(i)) { ++count; }
    }
 
    printf("answer: %d\n", (i - 2));
 
    return 0;
}
 
int isPrime(int num)
{
    int i;
 
    for (i = 3; i*i <= num; i += 2)
    {
        if (num%i == 0) { return 0; }
    }
 
    return 1;
}
 

소수인지 판별하는 함수를 홀수인 경우에 최적화하고,

홀수만 카운팅하는 방법이다.