백준 1929번 '소수 구하기' 알고리즘 설명

✨ Written with Claude

에라토스테네스의 체 (Sieve of Eratosthenes)

핵심 아이디어

소수의 배수를 모두 지워나가면 남는 수들이 소수다.

알고리즘 과정

1. 2부터 N까지 모든 수를 소수 후보로 설정
2. 2의 배수 제거 → 3의 배수 제거 → 5의 배수 제거...
3. √N까지만 확인하면 모든 합성수 처리 완료

핵심 최적화

• √N까지만: 합성수 N = a × b에서 a, b 중 하나는 반드시 √N 이하
• i²부터 시작: i × 2, i × 3, ... i × (i-1)은 이미 작은 소수들이 제거함
• 소수만 처리: 이미 제거된 수는 건너뜀

시간복잡도 비교

• 단순 방법: O((N-M+1) × √N) - 각 수마다 개별 소수 판별
• 에라토스테네스: O(N log log N) - 한 번에 모든 배수 제거

성능 차이 (실제 측정)

구현 (python)

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    
    return is_prime

M, N = map(int, input().split())
is_prime = sieve_of_eratosthenes(N)

for i in range(M, N + 1):
    if is_prime[i]:
        print(i)

구현 (c++)

#include <iostream>
#include <vector>
using namespace std;

vector<bool> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    return isPrime;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int M, N;
    cin >> M >> N;
    
    vector<bool> isPrime = sieveOfEratosthenes(N);
    
    for (int i = M; i <= N; i++) {
        if (isPrime[i]) {
            cout << i << '\n';
        }
    }
    
    return 0;
}

언제 사용할까?

• 범위 내 모든 소수 필요: 에라토스테네스의 체
• 단일 수 소수 판별: 단순 방법도 OK
• 여러 쿼리: 전처리 후 O(1) 조회

백준 1929번에서는 M ≤ N ≤ 1,000,000 이므로 에라토스테네스의 체가 유일한 정답
단순 브루트포스로는 시간 초과 발생