(C언어)프로젝트 오일러(Project Euler)7. 10001번째의 소수

문제

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.

이 때 10,001번째의 소수를 구하세요

코드

#include <stdio.h>

int main(void)
{
    int i, j;
    int count = 0;

    for (i = 1; i; i++)
    {
        for (j = 2; j < i; j++)
        {
            if (i % j == 0)
                break;
        }

        if (i == j)
            count++;
        
        if (count == 10001)
        {
            printf("%d\n", i);
            break;
        }
    }

    return 0;
}

판별할 수의 반까지만 본다거나 에라토스테네스의 체를 활용하여 소수를 구하기도 하던데, 그냥 기본적인 방법을 사용했다.

10001번째가 될 소수가 얼마나 클 지 몰라 i를 무한히 증가시켰다.

 

소수는 1과 자기자신만으로 나누어떨어지는 수이므로, 1로 나누면 무조건 나누어떨어진다. 따라서 j는 2부터 i보다 작을 때까지 증가시킨다.

i가 다른 수로 나누어떨어지면 반복을 중단한다.
중단되지 않고 j가 i와 같은 수가 되면 소수이다.이 때 몇 번째 소수인지 기록하기 위해 count를 1 증가시킨다.
count가 10001이 되면 i를 출력한다. 이 i가 10001번째 소수이다.

정답은 104743 이다.