[C++]프로젝트 오일러 7번 문제&풀이 (10001번째의 소수)

문제 7번

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

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

 

접근방법

1. 2부터 시작해서 충분히 큰 수까지 차례로 (=num)

2. 1부터 num까지 나눠본다.

3. 나머지가 0인게 2개일때만 소수이므로, 이때 카운팅을 한다. ( if (count==2) → check+1 )

4. 이렇게 카운팅 해서 10001번째 나오는 숫자가, 우리가 구하고자 하는 10001번째의 소수이다.

 

#include <iostream>

using namespace std;

int main()
{
    int count = 0; // 소수 판별
    int check = 1; // 몇 번째 소수인지

    for (int num = 2; num < 1000000000; num++)
    {
        for (int i = 1; i < num+1; i++)
        {
            if (num % i == 0)
            {
                count += 1;
            }
        }
        if (count == 2)
        {
            //cout <<check << "번째 소수 : " << num << endl;
            if (check == 10001)
            {
                cout << "최종 " << check << "번째 소수 : " << num << endl;
                break;
            }
            check++;
        }
        count = 0;
    }
    return 0;
}

개선점

• 충분히 큰 수를 위 코드에서는 1,000,000,000 (10억)으로 설정했는데, 10001번째 소수가 이보다 큰 값이면, 시행 값을 다시 설정해야 한다.
• '에라토스테네스의 체'를 사용하는 방법도 있다.

참고

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler