BOJ 2960 · 에라토스테네스의 체

알고리즘 분류 : 수학  

에라토스테네스의 체를 이용하는 문제이다. 자세한 내용은 이곳을 참조.

주어진 규칙에 따라 숫자를 지우면서, 숫자를 카운트하면 된다.

---

C++ 소스코드

#include <cstdio>

bool prime[1001];

int main() {
    int n, k;
    int cnt = 0;
    scanf("%d %d", &n, &k);
    for (int i=2; i<=n; i++) {
        for (int j=i; j<=n; j+=i) {
            if (!prime[j]) {
                prime[j] = true;
                if (++cnt == k) {
                    printf("%d\n", j);
                    break;
                }
            }
        }
    }
    return 0;
}

---

Python 3 소스코드

prime = [False for _ in range(1001)]

n, k = map(int, input().split())
cnt = 0
for i in range(2, n+1):
    for j in range(i, n+1, i):
        if prime[j] is False:
            prime[j] = True
            cnt += 1
            if cnt == k:
                print(j)
                break

---

참고

• 백준 온라인 저지 : BOJ 2960
• 위키피디아 : 에라토스테네스의 체