Problem 007

Problem 7 : 10001st prime (5%)

link

Description

original

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

간략해석

10001번째 소수를 구하여라.

Idea & Algorithm

naive idea

10001번째 소수를 에라토스테네스의 체를 이용해 구하면 된다.

advanced idea

소수정리에 따라 약 150,000이하에 10001번째 소수가 존재한다.

source code

예전에 풀어서 깃헙 코드는 이쁘지는 않아, 풀이 작성용으로 조금 수정했다.

#include <iostream>
using namespace std;
const int SZ = 200000;
int arr[SZ];

int main(){
    int cnt = 0;
    for(int i = 2 ; i < SZ; i++){
        if(arr[i]) continue;
        cnt++;
        if(cnt == 10001){
            cout << i << endl;
            return 0;
        }
        for(int j = 2 * i ; j < SZ ; j+=i){
            arr[j] = 1;
        }
    }
}