7. 에라토스테네스의 체

에라토스테네스의 체

빠른 설명

에라토스테네스의 체는 $1$부터 $N$까지의 소수를 빠르게 구하는 알고리즘이다. 소수를 발견하면 그 소수의 배수를 합성수로 지워 나간다.

언제 쓰는가

• $N$ 이하의 모든 소수가 필요할 때
• 여러 수에 대해 소수 여부를 반복해서 물을 때
• 약수, 배수, 소인수 관련 전처리가 필요할 때

시간복잡도

• 일반 구현: $O(N\log \log N)$
• 메모리: $O(N)$

참고자료

• CP-Algorithms - Sieve of Eratosthenes
• Wikipedia - Sieve of Eratosthenes
• GeeksforGeeks - Sieve of Eratosthenes
• 나무위키 - 에라토스테네스의 체

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    if (n >= 0) is_prime[0] = false;
    if (n >= 1) is_prime[1] = false;
 
    for (int i = 2; 1LL * i * i <= n; i++) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
    return is_prime;
}
 
int main() {
    auto is_prime = sieve(30);
    for (int i = 2; i <= 30; i++) {
        if (is_prime[i]) cout << i << ' ';
    }
}

Python 코드

def sieve(n):
    is_prime = [True] * (n + 1)
    if n >= 0:
        is_prime[0] = False
    if n >= 1:
        is_prime[1] = False
 
    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1
    return is_prime
 
is_prime = sieve(30)
print([i for i in range(2, 31) if is_prime[i]])