BOJ 1929 · 소수 구하기

알고리즘 분류 : 수학  

특정 범위 내에 존재하는 소수를 모두 구하는 문제이다. 여러 개의 소수를 구하기 위해서는, 에라토스테네스의 체를 이용하면 효율적이다.

• 2부터 N까지 구하고자 하는 소수를 모두 나열한다.
• 아직 지우지 않은 숫자 중, 가장 작은 숫자 P는 소수이다.
• P를 제외한 P의 배수를 모두 지운다.
• P보다 크고 루트 N보다 작거나 같은 숫자가 존재하는지 확인한다.
• 존재하면 두 번째, 세 번째 과정을 반복한다.
• 존재하지 않으면, 2부터 N사이에는 소수만 남아있다.
• M부터 N까지 존재하는 소수를 출력한다.

---

C++ 소스코드

#include <cstdio>

const int MAX = 1000000;
bool prime[MAX+1];

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

---

Python 3 소스코드

MAX = 1000000
prime = [False for _ in range(MAX+1)]
prime[1] = True

for i in range(2, MAX+1):
    if i*i > MAX:
        break
    if prime[i] is False:
        for j in range(i*i, MAX+1, i):
            prime[j] = True

m, n = map(int, input().split())
for i in range(m, n+1):
    if prime[i] is False:
        print(i)

---

참고

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