프로젝트 오일러(Project Euler) 7번문제

Problem 7

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

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

풀이

  개인적으로 이렇게 심플한 문제가 좋다. 소수 판별은 10001번째 까지만 구하면 되기 때문에, 그냥 숫자 하나씩 증가시키면서 나눠지는지 안나눠 지는지 테스트 하는 방식으로 진행하였다. 소수가 뭔지 모르는 사람은 없다고 생각한다.

#include <stdio.h>
 
int main()
{
    int num = 3, cnt = 1, flag = 0;
    // 3부터 소수판별 시작 -> count인 cnt는 1로 시작
    while (1)
    {
        for (int i = 2; i < num; i++)
        {
            if (num%i == 0)
            {
                flag = 1;    // 만약 1과 자기 자신 사이에 나눠지는
                break;        // 수가 있으면 플래그를 1로 올림.
            }
        }
        if (flag == 0) cnt++;    // 플래그가 0일때만 cnt 증가
        flag = 0;
 
        if (cnt == 10001)        // 10001번째 소수 출력
        {
            printf("%d\n", num);
            break;
        }
        num++;
    }
}

결과

  막코딩이라 그런가 빠르지는 않았다.