[BOJ] 백준 2960 에라토스테네스의 체

출처: https://www.acmicpc.net/problem/2960

 Input 
10 7

 Output 

9

▶ 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

    에라토스테네스의 체를 구현해서 제외되는 소수를 차례대로 구하는 문제입니다.

 

※ 관련 내용은 아래 링크 참고

소수 (Prime Number) 찾기 - 3

---

#include <iostream>
using namespace std;
 
const int MAX = 1001;
int N, K;
bool isPrime[MAX];
int solve(){
    // 모든 수를 소수로 가정
    for(int i = 2; i <= N; i++) {
        isPrime[i] = true;
    }
    
    int cnt = 0;
    for(int i = 2; i <= N; i++) {
        for(int j = i; j <= N; j += i) {
            // 이미 지워진 숫자인 경우
            if(!isPrime[j]) continue;
            
            // i의 배수 제거 (소수가 아닌 것 제거)
            isPrime[j] = false;
            ++cnt;
            if(cnt == K) {
                return j;
            }
        }
    }
}
 
int main() {
    cin >> N >> K;
    cout << solve() << endl;
    return 0;
}