백준 2960 에라토스테네스의 체

2960 에라토스테네스의 체

2960번: 에라토스테네스의 체

<에라토스테네스의 체>

소수 찾기 알고리즘 

n보다 작거나 같은 모든 소수를 찾기위해서

크기가 n+1인 배열을 선언한다

그리고 인덱스가 2의 배수면 1로 바꿔주고,n-1의 배수 까지 1로 바꾸면  

소수가 아닌 수는 값이 1이고 소수인 값은 0일 것이다.

 

이 문제는 소수를 찾는 것이 아닌 k번째로 지워진 수가 정답이다

이 문제에서는 n이 최대 1000이므로

int prime[1001]로 선언하였다.( 0으로 초기화 해준다.)

 

#include <iostream>
 
using namespace std;
 
int main(void)
{
    int n, k;
    int prime[1001];
 
    cin >> n >> k;
 
    for (int i = 0; i < 1001; ++i)
        prime[i] = -1;
 
    int a = 0;
    int ans = 0;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= (n / i); ++j) {
            if (prime[i*j] < 0) {
                prime[i*j] = 1;
                a++;
                if (a == k)
                    ans = i*j;
            }
        }
    }
    cout << ans << endl;
 
    return 0;
}