[15965번] K번째 소수

문제 출처 :

https://www.acmicpc.net/problem/15965

알고리즘 분석 :

문제 해결에 필요한 사항

1. 에라토스테네스의 체

우선 문제에서 최대 50만번째 소수까지 찾으면 된다 했으니 50만번째 소수를 찾아본 결과 750만 이전에서 끝이남을 알 수 있다.

따라서 소수를 구하는 에라토스테네스 체를 이용하여 소수를 구하고 최종적으로 N번째 소수를 출력하면 된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <memory.h>
#include <vector>
 
#define MAX_N 7500000
 
using namespace std;
 
int n = MAX_N;
bool isPrime[MAX_N + 1];
 
void eratosthenes()
{
    memset(isPrime, 1, sizeof(isPrime));
 
    isPrime[0] = isPrime[1] = false;
 
    int sqrtn = int(sqrt(n));
 
    for (int i = 2; i <= sqrtn; i++)
        if (isPrime[i])
            for (int j = i*i; j <= n; j += i)
                isPrime[j] = false;
}
 
vector<int> vc;
int main()
{
    eratosthenes();
    
    for (int i = 0; i <= MAX_N; i++)
        if (isPrime[i])
            vc.push_back(i);
 
    int n;
    cin >> n;
    cout << vc[n - 1];
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>