에라토스테네스의 체

1. 개요

2. 방법

3. 장점

4. 소스 코드

#!syntax cpp
#include <algorithm>
constexpr int MAX = 1000001;
bool prime[MAX];

// 일정 간격으로 특정 불린값으로 바꾸는 인라인 함수
inline void change_bool(int strt, int acc, bool flag){
    for(int i = strt; i < MAX; i += acc){
        prime[i] = flag;
    }
}

void eratosthenes(){
    std::fill_n(prime, MAX, false);//배열을 초기화한다.
    prime[2] = true;//2는 소수다.
    prime[3] = true;//3은 소수다. 이러면 5 이상의 홀수만 판별하면 된다.
    // 5 (mod 6) 과 1 (mod 6)을 참으로 설정한다. 이들은 2의배수도 아니고 3의 배수도 아닌 숫자집합이다.
    // 단, 1은 소수가 아니기에 1 (mod 6)은 7부터 시작한다.
    change_bool(5, 6, true);
    change_bool(7, 6, true);

    for (int i = 5, j = 25; j < MAX;){
        int nxt = (i - 3) % 6; // 현재의 i가 5 (mod 6) 이면 2, 1 (mod 6) 이면 4가 된다.
        if (prime[i] == true){
            int addi = i * 6; //i를 6배로 하여 x (mod 6)인 수만 검색하게 한다.

            // i * i 이상의 수를 지워나간다. 어차피 이 미만의 수들은 이미 소수 여부가 판별되었다.
            change_bool(j, addi, false);
            
            //이전 루프에서 누락된 부분을 마저 지워나간다.
            change_bool(nxt * i + j, addi, false); // nxt * i + j == i * ( i + nxt)
        }
        // 다음 루프 진행을 위한 준비. 현재의 i가 5 (mod 6) 이면 2를, 1 (mod 6)이면 4를 더한다.
        i += nxt;
        j = i * i;
    }
}

#!syntax python
def eratosthenes(num:int = 1000000):
    MAX = num + 1
    LIM = int(num ** 0.5) + 1
    RSET = lambda strt, end, gap: set(range(strt, end, gap))
    
    # 5 (mod 6)과 1 (mod 6)을 참으로 설정한다. 이들은 2의 배수도 아니고 3의 배수도 아닌 숫자집합이다.
    # 단, 1은 소수가 아니기에 1 (mod 6)은 7부터 시작한다.
    prime = RSET(5, MAX, 6) | RSET(7, MAX, 6)
    if num > 2: prime.add(3) # 3 추가
    if num > 1: prime.add(2) # 2 추가
    for i in range(5, LIM, 6):
        # 5 (mod 6) 부분
        if i in prime:
            prime -= RSET(i * i, MAX, i * 6) | RSET(i * (i + 2), MAX, i * 6)
        # 1 (mod 6) 부분
        j = i + 2
        if j in prime:
            prime -= RSET(j * j, MAX, j * 6) | RSET(j * (j + 4), MAX, j * 6)

    return prime

5. 관련 문서

• 노가다(수학)
• 리만 가설
• 에라토스테네스
• 정수론
• 소수(수론)
• 마지막 구호 생략