[Project Euler #7][C++] 10001번째의 소수

문제7: 10001번째의 소수

문제

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

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

문제 해결 방법

• 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.
  • 2중 for문을 사용하여
    • 1부터 N까지 순회를 하면서 소수의 조건(나머지가 1과 그 자신인 수) 을 만족시키는 수가 발견될 경우 count의 값을 1씩 증가시켰다.
    • count의 값이 NUM(10001)이 되었을 때의 값을 ans 변수에 할당하고, 2중 for문에서 빠져나오도록 하였다.
  • NUM(10001)번째 소수가 담긴 ans 변수의 값을 출력하도록 하였다.
• 연산을 빠르게 하도록 하기 위해 register 변수를 사용하여 for문을 순회하도록 하였다.

소스 코드

#include <iostream>
using namespace std;
 
#define N 100000000
#define NUM 10001   // NUM 번째 소수
 
int main() {
    int count_remainder = 0, count = 0;
    unsigned long long int ans;
 
    for (register int i = 1; i <= N; i++) {
        for (register int j = 1; j <= i; j++) {                                                                    
            if (i % j == 0) {
                count_remainder++;
            }
        }
        if (count_remainder == 2) {
            count++;
            count_remainder = 0;
        }
        else {
            count_remainder = 0;
        }
        if (count == NUM) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

정답

104743

심화 공부

에라토스테네스의 체(The Sieve of Eratosthenes)

주어진 자연수 n까지의 모든 소수를 찾는 고대의 알고리즘이다. 첫 소수인 2부터 시작해서 각 소수의 배수가 되는 합성수를 제거하는 방법을 반복하여 모든 소수를 걸러낸다. 작은 범위에서 모든 소수를 찾아내는 가장 효율적인 방법 중 하나이다.

알고리즘

1. 2부터 n까지의 모든 자연수의 목록을 만든다: (2, 3, 4, ..., n).

2. 초기 상태에 변수 p 값으로 최소 소수인 2를 대입한다.

3. 2p에서 n까지 모든 p의 배수를 목록에서 찾아 제거 표시한다: (2p, 3p, 4p, ...; p는 제외).

4. p보다 큰 수 중에서 제거 표시가 안 된 가장 작은 수를 찾는다. 그런 수가 없다면 종료하고, 있다면 그 수를 p에 대입하고 3번부터 다시 반복한다.

5. 알고리즘이 종료할 때, 목록에서 제거 표시가 되지 않고 남아 있는 수들이 n까지의 모든 소수이다.

6. 에라토스테네스의 체는 소수의 개수 를 세는 데도 사용될 수 있다.

---

문제 출처 : https://euler.synap.co.kr/problem=7