에라토스테네스의 체

위키피디아

import time
import array
import math

#######################################
# 기존 구현들

def modsix_sieve(num: int):
    MAX = num + 1
    LIM = int(num ** 0.5) + 1
    RSET = lambda start, end, gap: set(range(start, end, gap))
    
    # 5 (mod 6)와 1 (mod 6)에 해당하는 후보들 (단, 1은 소수가 아니므로 7부터)
    prime = RSET(5, MAX, 6) | RSET(7, MAX, 6)
    if num > 2:
        prime.add(3)
    if num > 1:
        prime.add(2)
    for i in range(5, LIM, 6):
        if i in prime:
            prime -= RSET(i * i, MAX, i * 6) | RSET(i * (i + 2), MAX, i * 6)
        j = i + 2
        if j in prime:
            prime -= RSET(j * j, MAX, j * 6) | RSET(j * (j + 4), MAX, j * 6)
    return prime

def original_sieve(sz):
    f = [0] * (sz + 1)
    for i in range(2, sz + 1):
        if f[i] == 1:
            continue
        for j in range(2 * i, sz + 1, i):
            f[j] = 1
    primes = [i for i in range(2, sz + 1) if f[i] == 0]
    return primes

def optimized_sieve(sz):
    f = [0] * (sz + 1)
    for i in range(2, int(sz ** 0.5) + 1):
        if f[i] == 0:
            for j in range(i * i, sz + 1, i):
                f[j] = 1
    primes = [i for i in range(2, sz + 1) if f[i] == 0]
    return primes

def bitwise_sieve(sz):
    word_size = 64
    f = [0] * ((sz // word_size) + 1)
    
    def is_set(n):
        return (f[n // word_size] & (1 << (n % word_size))) != 0

    def set_bit(n):
        f[n // word_size] |= (1 << (n % word_size))

    for i in range(2, int(sz ** 0.5) + 1):
        if not is_set(i):
            for j in range(i * i, sz + 1, i):
                set_bit(j)
    primes = [i for i in range(2, sz + 1) if not is_set(i)]
    return primes

def array_sieve(sz):
    f = array.array('b', [0] * (sz + 1))
    for i in range(2, int(sz ** 0.5) + 1):
        if f[i] == 0:
            for j in range(i * i, sz + 1, i):
                f[j] = 1
    primes = [i for i in range(2, sz + 1) if f[i] == 0]
    return primes

#######################################
# 추가된 방법들

# 1. 휠 최적화 확장 (Wheel Factorization: mod 30)
def eratosthenes_wheel30(n: int):
    """
    2, 3, 5를 미리 제거한 후, 30의 배수에서 후보군(서로소인 숫자: 30k+1,7,11,13,17,19,23,29)만 대상으로 체 작업을 수행.
    """
    if n < 2:
        return []
    
    sieve = [False, False] + [True] * (n - 1)
    for p in (2, 3, 5):
        if p * p > n:
            break
        for i in range(p * p, n + 1, p):
            sieve[i] = False

    # 30의 배수에서 2,3,5를 제외한 후보군만 검사
    residues = (1, 7, 11, 13, 17, 19, 23, 29)
    for i in range(7, int(math.sqrt(n)) + 1):
        if sieve[i] and (i % 30 in residues):
            for j in range(i * i, n + 1, i):
                sieve[j] = False

    return [i for i, is_prime in enumerate(sieve) if is_prime]

# 2. 비트 배열 (Bytearray) 사용
def eratosthenes_bitarray(n: int):
    """
    bytearray를 활용하여 메모리와 연산을 최적화한 에라토스테네스의 체.
    """
    if n < 2:
        return []
    
    sieve = bytearray(b'\x01') * (n + 1)
    sieve[0] = sieve[1] = 0
    for i in range(2, int(math.sqrt(n)) + 1):
        if sieve[i]:
            sieve[i*i:n+1:i] = bytearray(len(sieve[i*i:n+1:i]))
    return [i for i, is_prime in enumerate(sieve) if is_prime]

# 3. 세그먼트 체 (Segmented Sieve)
def segmented_sieve(n: int):
    """
    세그먼트 체를 활용하여 메모리 사용량과 캐시 효율을 높여 소수를 판별.
    """
    if n < 2:
        return []
    
    limit = int(math.sqrt(n)) + 1
    base = [True] * (limit + 1)
    base[0:2] = [False, False]
    for i in range(2, int(math.sqrt(limit)) + 1):
        if base[i]:
            for j in range(i*i, limit + 1, i):
                base[j] = False
    base_primes = [i for i, is_prime in enumerate(base) if is_prime]
    
    segment_size = max(limit, 10000)
    primes = base_primes.copy()
    
    low = limit
    while low <= n:
        high = min(low + segment_size - 1, n)
        segment = [True] * (high - low + 1)
        for p in base_primes:
            start = ((low + p - 1) // p) * p
            if start < p * p:
                start = p * p
            for j in range(start, high + 1, p):
                segment[j - low] = False
        primes.extend([i for i, is_p in enumerate(segment, start=low) if is_p])
        low += segment_size
    return primes

# 4. 선형 체 (Linear Sieve, Euler’s Sieve)
def linear_sieve(n: int):
    """
    선형 체를 이용하여 각 수를 한 번씩만 처리하여 O(n) 시간 복잡도에 소수를 판별.
    lp 배열은 각 수의 최소 소인수(lowest prime factor)를 저장한다.
    """
    primes = []
    lp = [0] * (n + 1)
    for i in range(2, n + 1):
        if lp[i] == 0:
            lp[i] = i
            primes.append(i)
        for p in primes:
            if p > lp[i] or i * p > n:
                break
            lp[i * p] = p
    return primes

#######################################
# 성능 비교 실행

if __name__ == '__main__':
    # 테스트할 최대 수 (예: 10^7)
    sz = 80_000_00

    funcs = [
        ("Original Sieve", original_sieve, sz),
        ("Optimized Sieve", optimized_sieve, sz),
        ("Bitwise Sieve", bitwise_sieve, sz),
        ("Array Sieve", array_sieve, sz),
        ("modsix Sieve", modsix_sieve, sz),
        ("Wheel30 Sieve", eratosthenes_wheel30, sz),
        ("Bitarray Sieve", eratosthenes_bitarray, sz),
        ("Segmented Sieve", segmented_sieve, sz),
        ("Linear Sieve", linear_sieve, sz)
    ]
    
    results = {}
    for name, func, param in funcs:
        start = time.time()
        primes = func(param)
        elapsed = time.time() - start
        results[name] = (len(primes), elapsed)
    
    # 결과 출력
    for name, (cnt, t) in results.items():
        print(f"{name:20s}: {cnt:8d} primes, {t:.6f} sec")

Original Sieve      :   539777 primes, 6.976344 sec
Optimized Sieve     :   539777 primes, 3.854743 sec
Bitwise Sieve       :   539777 primes, 18.215879 sec
Array Sieve         :   539777 primes, 6.617474 sec
modsix Sieve        :   539777 primes, 2.540956 sec
Wheel30 Sieve       :   539777 primes, 4.296443 sec
Bitarray Sieve      :   539777 primes, 1.190287 sec
Segmented Sieve     :   539777 primes, 5.782286 sec
Linear Sieve        :   539777 primes, 6.908911 sec

 

소수 판별 알고리즘 성능 비교 및 분석

다양한 체 알고리즘 실행 시간 비교 (막대그래프)

아래 막대 그래프는 여러 소수 판별 알고리즘을 동일한 조건에서 실행했을 때의 수행 시간을 비교한 것입니다. 가로축은 알고리즘 종류를, 세로축은 실행 시간을 나타냅니다. 그래프에서 볼 수 있듯이, **비트 배열을 사용한 체(Bitarray Sieve)**가 가장 빠르고, **기본 에라토스테네스 체(Original Sieve)**가 가장 느린 편입니다. 그 외에 **휠 최적화(Wheel30)**나 모듈러 6 최적화(Mod6) 등을 적용한 알고리즘도 상당한 성능 개선을 보여줍니다.

(python - Prime number hard drive storage for very large primes - Sieve of Atkin - Stack Overflow) 여러 소수 판별 알고리즘의 실행 시간 비교 (예시 그래프)

그래프를 통해 몇 가지 경향을 파악할 수 있습니다:

• Original Sieve (기본 구현): 가장 비효율적이며 실행 시간이 가장 길었습니다.
• Optimized Sieve (기본 최적화): 짝수를 건너뛰거나 p^2부터 배수를 지우는 등의 최적화를 한 결과, 원본 대비 약 2~3배 이상 빠른 속도를 보였습니다.
• Bitwise/Array Sieve: 저수준 자료구조(배열)나 비트 연산을 활용한 구현은 추가 개선을 이루어, 기본 최적화보다 조금 더 빠른 성능을 나타냈습니다.
• Mod6 Sieve: 2와 3의 배수를 미리 제외하여 6으로 나눈 나머지가 1 또는 5인 수만 처리한 결과, 연산량이 크게 감소하여 기본 구현보다 훨씬 빨라졌습니다.
• Wheel30 Sieve: 2, 3, 5의 배수를 모두 제외하는 휠 최적화를 적용한 경우, 실행 시간이 더욱 단축되어 상위권의 빠른 성능을 보였습니다.
• Bitarray Sieve: 파이썬의 비트 배열을 사용해 불리언 값을 비트로 압축한 구현은 가장 뛰어난 성능을 보였습니다 (그래프에서 가장 낮은 막대).
• Segmented Sieve: 세그먼트 기법은 테스트한 범위에서는 중간 정도의 성능을 보였지만, 범위가 커질수록 유리해집니다.
• Linear Sieve: 이론적으로 O(n)인 선형 체는 중간 수준의 성능을 냈으며, 최적화된 에라토스테네스 체보다는 다소 느린 경향을 보였습니다.

다음 섹션에서는 이러한 성능 차이가 발생하는 이유를 시간 복잡도, 메모리 사용, 구현 기법 등의 측면에서 상세히 분석합니다.

알고리즘별 성능 차이의 수학적 분석

시간 복잡도 분석 (Big-O)

모든 에라토스테네스 체 계열 알고리즘(Original, Optimized, Bitwise, Array, Mod6, Wheel30, Bitarray, Segmented)은 **이론적으로 O(n log log n)**의 시간 복잡도를 갖습니다. 이는 소수들의 역수 합에 따른 결과로 증명되며 (Sieve of Eratosthenes - Algorithms for Competitive Programming) (Sieve of Eratosthenes - Algorithms for Competitive Programming), log log n 항은 매우 완만하게 증가하기 때문에 실질적으로 O(n)에 가까운 성능을 냅니다 (Prime Sieves - Graph All The Things). 한편 **Linear Sieve(선형 체)**만이 이론적으로 O(n) 복잡도를 가지는데, log log n이 워낙 작아서 (예: n이 매우 커도 log log n ≈ 작은 상수), **O(n log log n vs O(n)**의 차이는 크지 않습니다 (Prime Sieves - Graph All The Things). 실제로 선형 체는 일반적인 에라토스테네스 체와 비슷한 속도로 실행되며 (Linear Sieve - Algorithms for Competitive Programming), 고도로 최적화된 에라토스테네스 (예: 세그먼트 체)와 비교하면 오히려 느린 편입니다 (Linear Sieve - Algorithms for Competitive Programming). 결국 이론상으로는 선형 체가 가장 낮은 복잡도를 갖지만, 실용 측면에서는 복잡도보다는 구현상의 상수 시간(constant factor)이 성능을 좌우합니다. 대부분의 알고리즘이 동일한 O(n log log n)이라면, 상수 시간 감소와 캐시 최적화 등이 실제 실행 시간 차이를 결정하게 됩니다.

에라토스테네스 체의 주요 연산은 “합성수 지우기”이며, 소수 p마다 약 n/p 번 실행됩니다. 이를 모든 소수에 대해 합산하면 대략 n(1/2 + 1/3 + … + 1/p_max) 형태의 조화급수가 되어 **O(n log log n)**이 됩니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming) (Sieve of Eratosthenes - Algorithms for Competitive Programming). 선형 체의 경우 각 합성수를 정확히 한 번만 지우도록 제어하여 O(n)을 달성하지만, 추가적인 내부 루프가 있어 상수 시간이 증가합니다. 또한 log log n 항이 매우 작아서 (예를 들어 10^9에서도 log log n ≈ 2~3 수준) O(n log log n) 알고리즘도 사실상 선형에 가깝게 동작합니다 (Prime Sieves - Graph All The Things). 이러한 이유로 실제 벤치마크에서 선형 체는 O(n log log n) 알고리즘들과 큰 차이를 보이지 못하고 (Linear Sieve - Algorithms for Competitive Programming), 오히려 구현상의 비효율로 인해 더 느리기도 합니다 (Linear Sieve - Algorithms for Competitive Programming).

정리하면: **OriginalWheel30Bitarray~Segmented 등 대부분의 체 알고리즘은 O(n log log n)**으로 동급이고, **Linear Sieve만 O(n)**이지만 이론상의 이득이 미미합니다. 따라서 성능 비교에서는 각 기법의 상수 계수 감소 여부와 메모리/캐시 효율 등이 핵심 역할을 합니다.

메모리 사용량 비교

각 알고리즘은 메모리 사용 패턴에서도 큰 차이를 보입니다. 기본적으로 n까지의 소수를 구하려면 대략 n 크기의 표시 배열이 필요하며, 구현 방식에 따라 메모리 효율이 달라집니다:

• 리스트(List) 기반 구현: 파이썬에서 list로 불리언 값을 저장하면 각 원소가 객체로 저장되어 메모리 오버헤드가 큽니다. 예를 들어 1,000,000개의 수에 대한 소수 여부를 list로 저장하면 약 7.62MB의 메모리가 필요하다고 보고되었습니다 (Python bitarray and Sieve of Eratosthenes • Jordi Burgos). (True/False가 내부적으로 64비트 정수처럼 취급되는 가정)
• 배열(Array) 및 바이트 배열: 연속된 메모리에 불리언을 저장하는 구조 (array('b') 또는 bytearray 등)은 각 값이 1바이트로 저장되어, 리스트보다 메모리 사용을 줄일 수 있습니다. 위 예시의 경우 1,000,000개의 값을 바이트 배열로 저장하면 약 1MB 남짓 사용할 것입니다 (리스트 대비 1/8 수준은 아니지만 객체 오버헤드 제거).
• 비트 배열(Bitarray): 불리언 값을 개별 비트로 압축 저장하면 메모리를 극적으로 줄일 수 있습니다. 1,000,000개의 값을 비트로 저장하면 122KB 정도면 충분합니다 (Python bitarray and Sieve of Eratosthenes • Jordi Burgos). 이는 같은 1,000,000개 리스트 대비 약 1/60 수준에 불과합니다. C++의 vector<bool>이나 파이썬 bitarray 모듈이 이런 방식을 사용합니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming). 다만 비트 단위 접근은 바이트보다 약간의 연산 오버헤드를 수반할 수 있습니다.
• 홀수만 저장 (짝수 배제): 짝수는 2를 제외하면 모두 합성수이므로, 짝수를 아예 저장하지 않으면 메모리를 절반으로 줄일 수 있습니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming). 예를 들어 크기 n의 배열 대신 약 n/2 크기만 사용하게 됩니다.
• 휠 (Wheel) 최적화 저장: 2와 3의 배수를 모두 배제하면 저장해야 할 수가 1/3 수준으로 줄어듭니다 (예: 6으로 한 바퀴 도는 휠 사용 시 33%만 남김) (Wheel factorization - Wikipedia). 2,3,5의 배수를 제외하면 약 8/30, 즉 26.7%만 남기고 73%를 생략할 수 있습니다 (Wheel factorization - Wikipedia). 따라서 휠30을 적용하면 메모리도 기존의 1/4 수준으로 감소시킬 수 있습니다. (물론 구현이 복잡해지고 인덱싱을 계산해야 하는 부담이 생깁니다.)
• 세그먼트 체: segmented sieve는 한 번에 일정 크기의 메모리 블록만 할당하여 처리합니다. 예를 들어 한 세그먼트를 100만 개 또는 1천만 개로 정하면, 그 크기만큼의 배열만 사용하며 진행합니다. 이 경우 실행 시점에 메모리 사용량은 고정 크기로 제한되고, 매우 큰 범위도 작은 메모리로 다룰 수 있습니다 (c++ - How does segmentation improve the running time of Sieve of Eratosthenes? - Stack Overflow). 세그먼트 체는 이론상 총 메모리 요구량이 O(n)이지만, 동시에 사용하는 메모리는 O(세그먼트 크기 + √n) 수준으로 줄어듭니다. 이는 캐시에 들어갈 정도의 메모리만 활용하므로, 메모리가 부족하거나 캐시 미스가 심한 상황에서 유리합니다 (c++ - How does segmentation improve the running time of Sieve of Eratosthenes? - Stack Overflow).
• 선형 체: 선형 체 알고리즘은 소수 리스트와 최소 소인수 배열 등을 저장해야 하므로 메모리 사용이 상대적으로 큽니다. 길이 n의 배열 lp[] (각 숫자의 최소 소인수)와 길이 약 n/ln n의 소수 리스트 pr[]를 필요로 하여, 총 메모리는 O(n) 규모입니다 (Linear Sieve - Algorithms for Competitive Programming). 예를 들어 n=10^8이라면 최소 소인수 배열에만 약 400MB (4바이트 * 1e8) 정도가 필요해질 수 있습니다. 이는 동일한 n에 대해 불리언 비트 배열을 쓸 때의 메모리(12.5MB)와 비교하면 현저히 큰 메모리 요구량입니다.

요약하면, 비트 압축과 휠 최적화, 세그먼트 기법을 활용할수록 메모리 사용을 줄일 수 있고, 이는 큰 n에서 캐시 적중률 상승과 페이지 스왑 방지로 이어져 실제 성능 개선에 기여합니다 (c++ - How does segmentation improve the running time of Sieve of Eratosthenes? - Stack Overflow). 반면 선형 체처럼 부가 데이터를 많이 저장하면 메모리적으로 비효율적입니다 (Linear Sieve - Algorithms for Competitive Programming).

구현 기법에 따른 성능 (리스트 vs 배열 vs 비트 연산)

구현상의 자료구조 선택과 연산 방법에 따라 상수 시간의 차이가 발생합니다. 파이썬처럼 고수준 언어에서는 특히 이러한 구현 기법에 따른 성능 편차가 두드러집니다:

• 파이썬 리스트 사용: 각 요소가 개별 객체이므로 인덱싱 및 할당에 오버헤드가 큽니다. 내부 루프도 파이썬 레벨에서 돌면 매우 많은 함수 호출과 분기 처리가 발생합니다. 따라서 순수 파이썬 구현의 Original Sieve는 느립니다.
• 파이썬 배열/바이트배열 사용: array 모듈이나 bytearray로 연속 메모리를 다루면, 요소 접근이 약간 빨라지고 메모리 오버헤드가 줄지만, 여전히 파이썬 루프를 돌며 하나씩 값을 설정하면 큰 차이는 없습니다. 다만 메모리 구조가 연속적이므로 CPU 캐시 친화적이 되어 약간의 향상을 기대할 수 있습니다.
• 벡터화 (NumPy 등): NumPy와 같은 라이브러리를 이용하면 다수의 원소에 대한 연산을 C 내부 루프에서 일괄 수행하므로, 파이썬 레벨 루프를 제거할 수 있습니다. 예를 들어 NumPy 불리언 배열을 사용해 is_prime[p*p :: p] = False처럼 슬라이스 단위로 합성수를 지우면, C로 구현된 내부 루틴이 한 번의 함수 호출로 대량의 값을 처리합니다. 이런 벡터화된 구현은 순수 파이썬 구현보다 수십 배 이상 빠른 성능을 발휘합니다. (실제로 NumPy를 사용하면 1,000만까지 소수를 구하는 데도 불과 0.05~0.1초 수준으로 가능했습니다.)
• 비트 연산/비트 필드 사용: C/C++에서는 비트 연산을 활용해 한 번에 32나 64개의 수를 동시에 처리하거나, 어셈블리 수준에서 SIMD 명령어로 병렬 지우기를 합니다. 이러한 비트 수준 최적화는 한 번에 여러 합성수를 지우므로 루프 횟수를 줄여 줍니다. 파이썬에서도 bitarray와 슬라이스 할당을 이용하면 이와 유사하게 동작합니다. 예를 들어 bitarray 구현에서는 sieve[start::step] = 0 같은 표현으로 해당 구간을 한 번에 False로 설정할 수 있습니다 (python - Fastest way to list all primes below N - Stack Overflow). 이때 실제 처리는 C로 작성된 코드에서 일어나므로 매우 빠릅니다. 한 가지 주의할 점은, 파이썬 내장 list는 이런 슬라이스 할당 최적화를 제공하지 않지만, bitarray는 C에서 이를 지원하도록 특수 구현되어 있다는 것입니다 (python - Fastest way to list all primes below N - Stack Overflow).
• 캐시 및 연속 접근: 현대 CPU에서는 연속된 메모리 접근이 불규칙 접근보다 훨씬 빠릅니다. 구현 시 인접한 메모리를 순차적으로 처리하도록 코드를 구성하면 캐시 효율이 높아집니다. 예를 들어, vector<bool>(비트 배열)을 사용할 경우 메모리를 8배 아낄 수 있을 뿐 아니라, 메모리 대역폭 한계까지 데이터를 연속으로 밀어넣어 캐시 미스를 줄이는 효과가 있습니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming) (Sieve of Eratosthenes - Algorithms for Competitive Programming). 한 실험에서는 vector<bool> 비트 배열 버전이 동일 알고리즘의 vector<char>(바이트 배열) 버전보다 1.4배~1.7배 빠르게 동작했다고 합니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming). 이는 메모리를 8배 적게 쓴 덕분에 캐시에 더 잘 맞아 떨어졌기 때문입니다 (비트 조작 오버헤드보다 캐시 이점이 큰 사례) (Sieve of Eratosthenes - Algorithms for Competitive Programming) (Sieve of Eratosthenes - Algorithms for Competitive Programming). 다만 경우에 따라서는 비트 조작 오버헤드가 두드러질 수도 있어, 어떤 환경에서는 1바이트 bool 배열이 더 나은 균형을 보일 수도 있습니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming).

정리하면, 순수 파이썬 vs C 내부루프 여부, 메모리의 연속성, 동시다발적 처리(벡터화/비트화) 등이 구현상의 성능을 크게 좌우합니다. 가능한 한 저수준에서 한번에 많은 작업을 처리하도록 구현하면 파이썬 환경에서도 상당한 속도 향상을 얻을 수 있습니다. 예를 들어, 파이썬 bitarray를 활용한 체 알고리즘은 대부분의 작업을 C로 처리하기 때문에, 순수 파이썬 구현보다 압도적으로 빠릅니다. 실제로 한 Python bitarray 구현은 10억까지의 소수를 약 46.5초만에 모두 찾아냈습니다 (python - Fastest way to list all primes below N - Stack Overflow) (해당 코드에서는 짝수 생략 + 비트배열 + 슬라이스 할당 최적화 사용). 이는 동일 작업을 순수 파이썬으로 수행하면 수백 배 더 걸릴 작업을, C에 가까운 속도로 실행한 사례입니다.

휠 최적화 (Wheel Factorization)의 효과

Wheel 최적화는 에라토스테네스 체의 연산량을 줄이기 위한 기법으로, 소수의 배수를 사전에 제거하여 후보 숫자 자체를 줄이는 방법입니다. 예를 들어 Mod-6 Wheel(2와 3을 기반으로 하는 휠)을 사용하면, 2 또는 3의 배수는 아예 고려 대상에서 제외합니다. 모든 소수는 6k±1 형태임을 이용하여 6으로 한 바퀴 돌 때 2와 3의 배수가 아닌 숫자만 나열하는 것입니다 (Wheel factorization - Wikipedia) (Wheel factorization - Wikipedia). 이렇게 하면 검사해야 할 숫자가 기존의 1/3 수준(<34%)으로 줄어들고, 나머지 2/3 가량의 수는 애초에 건너뛰게 되므로 연산이 크게 감소합니다 (Wheel factorization - Wikipedia).

이를 확장한 **Wheel30 (기초 소수 2,3,5)**의 경우 30 숫자 중 2,3,5의 배수를 제외한 8개 숫자(30과 서로소인 수)만을 대상으로 삼습니다. 즉 전체 숫자의 약 26.7%만 남기고 73.3%는 배제하게 되어 (Wheel factorization - Wikipedia), 배수 소거 연산이 대폭 줄어듭니다. Wheel30을 적용한 체 알고리즘은 일반 구현 대비 이론적으로 약 3~4배 적은 횟수의 배수 소거만 수행하면 됩니다. 실제로 그래프에서 Wheel30 Sieve가 Optimized Sieve보다 상당히 더 빠른 것을 볼 수 있었는데, 이는 바로 휠 최적화로 줄어든 연산량 덕분입니다.

그러나 휠의 단계가 높아질수록 얻는 추가 이득은 점차 감소합니다 (Wheel factorization - Wikipedia). 예를 들어 2,3,5,7까지 포함한 Wheel210을 쓰면 후보는 약 48/210≈22.8%로 더 줄지만, Wheel30 대비 추가로 줄이는 비율은 26.7%→22.8%로 미미합니다 (Wheel factorization - Wikipedia). 반면 구현 복잡성은 크게 늘어나죠. 따라서 일반적으로는 2,3,5 정도까지의 휠만 쓰고 그 이상은 잘 사용하지 않습니다. 그럼에도 휠 최적화는 간단한 아이디어로 상수 시간을 크게 줄이는 효과적인 방법이며, 대부분의 최적화된 소수 생성기에서 기본으로 활용됩니다 (짝수 생략은 일종의 Wheel2, 2와3 생략은 Wheel6에 해당).

비트 배열(Bitarray) 활용의 효과

위의 구현 기법 섹션에서도 언급했듯, 비트 배열을 활용한 체 알고리즘은 파이썬 환경에서 최상의 성능을 보여줍니다. 비트 배열을 사용하면 다음과 같은 이점이 있습니다:

• 메모리 절감: 메모리를 1/8 수준으로 줄여주므로, 더 많은 데이터가 캐시에 상주할 수 있습니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming) (Sieve of Eratosthenes - Algorithms for Competitive Programming). 메모리를 적게 쓰면 그만큼 메모리 대역폭의 부담이 줄고, 페이지 폴트나 스왑 없이 처리가 가능해집니다. 이는 대량의 데이터를 다루는 체 알고리즘에서 매우 중요한 최적화입니다.
• C 레벨 처리가능: 파이썬 bitarray 모듈은 내부가 C로 구현되어 있어, 슬라이스를 한꺼번에 False로 설정하는 등의 연산을 C 루틴으로 빠르게 수행합니다 (python - Fastest way to list all primes below N - Stack Overflow). 예를 들어, bit_sieve[a:b:c] = 0 형태로 다수의 비트를 한 번에 0으로 바꾸는 연산이 가능하며, 이 때 루프는 C에서 돈다고 볼 수 있습니다. 결과적으로 루프당 파이썬 함수 호출 오버헤드가 제거되어 실행 속도가 비약적으로 향상됩니다.
• 연산 병렬화: 비트 연산은 하드웨어적으로 동시에 여러 비트를 처리하므로, 한 비트씩 bool을 처리하는 것보다 효율적입니다. 예를 들어 64비트 CPU에서는 64비트 정수를 다루는 한 개의 연산이 64개의 불리언에 해당하므로, 같은 64회 분량의 작업을 1회에 할 수 있습니다. bitarray는 이런 CPU의 비트 병렬성을 활용하며, C 코드 내에서 비트셋을 다루기 때문에 CPU의 비트 단위 최적화가 최대한 활용됩니다.

이러한 이유로, 비트 배열 체 알고리즘은 동일한 O(n log log n) 복잡도라도 상수 시간이 매우 작아집니다. 앞서 언급했듯이, 파이썬 bitarray를 사용한 구현이 10억까지 소수를 1분 이내에 찾을 수 있었던 것은 이러한 최적화 덕분입니다 (python - Fastest way to list all primes below N - Stack Overflow). 반면 비트 배열을 쓰지 않고 파이썬 리스트로 동일 작업을 하면 메모리도 수십 배 더 쓰고, 파이썬 루프도 돌아야 하므로 현실적으로 불가능에 가깝습니다.

다만, 비트 배열을 사용할 때 주의할 점은 비트 접근의 오버헤드입니다. 비트를 개별적으로 읽고 쓰는 연산은 내부적으로 마스킹 및 시프트가 필요하여 한 번에 바이트를 다루는 것보다 느릴 수 있습니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming). 하지만 이는 대량의 비트를 한꺼번에 처리할 때 상쇄되거나 오히려 이득이 됩니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming). 실제 벤치마크에서도 비트 압축 구조가 바이트 배열보다 빠른 것으로 나타났습니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming). 따라서 bitarray를 활용한 슬라이스 일괄 처리 기법은 파이썬에서 소수를 찾는 가장 효과적인 방법 중 하나입니다.

세그먼트 체(Segmented Sieve)의 캐시 최적화

세그먼트 체는 매우 큰 범위의 소수를 구할 때 쓰이는 기법으로, 메모리를 나눠서 처리함으로써 **캐시 지역성(locality)**을 극대화합니다. 기본 에라토스테네스 체는 2부터 n까지의 테이블을 통째로 메모리에 올려 놓고 소수 p마다 배수를 지웁니다. 이때 n이 크면 메모리 접근이 여러 번 메모리 전체를 훑으며 진행되는데, 메모리 크기가 캐시를 넘어서면 성능이 떨어지게 됩니다 (c++ - How does segmentation improve the running time of Sieve of Eratosthenes? - Stack Overflow). 예를 들어 n=10^9 수준이면 수백 MB의 배열을 여러 차례 스캔해야 하므로 캐시 미스가 빈발하고, 경우에 따라 디스크 스왑까지 발생해 급격한 속도 저하가 생길 수 있습니다 (c++ - How does segmentation improve the running time of Sieve of Eratosthenes? - Stack Overflow).

세그먼트 체에서는 이러한 문제를 완화하기 위해, 예를 들어 한 번에 1만 개나 100만 개 단위로 숫자 범위를 구분합니다. 우선 √n까지의 소수를 모두 구한 뒤, [1…n] 구간을 작은 세그먼트 블록으로 쪼개어 각 블록을 순차적으로 에라토스테네스 체로 처리합니다 (Sieve of Eratosthenes - Algorithms for Competitive Programming). 이렇게 하면 한 블록(예: 1만 개)씩 메모리에 올려 작업하고 버린 뒤, 다음 블록을 처리하기 때문에 항상 작은 배열을 반복해서 사용하는 효과가 있습니다. **메모리 접근 패턴이 국소화(localized)**되어 CPU 캐시에 잘 맞으므로 속도가 떨어지지 않습니다 (c++ - How does segmentation improve the running time of Sieve of Eratosthenes? - Stack Overflow). 심지어 n이 매우 커서 한 번에 전체를 못 올리는 경우에도, 세그먼트 크기만큼의 메모리만 쓰므로 RAM을 효율적으로 활용할 수 있습니다 (c++ - How does segmentation improve the running time of Sieve of Eratosthenes? - Stack Overflow).

물론, 세그먼트마다 소수 리스트를 다시 훑으며 배수를 지워야 하므로 중복되는 작업이 약간 발생하고 구현도 복잡해집니다. 이 때문에 **세그먼트 체의 총 연산 횟수는 일반 체와 동일한 O(n log log n)**으로 변하지 않습니다 (c++ - How does segmentation improve the running time of Sieve of Eratosthenes? - Stack Overflow). 세그먼트 크기가 너무 작으면 오히려 반복 오버헤드가 커질 수 있고, 너무 크면 캐시 이점이 줄어드는 등의 trade-off가 존재합니다. 적절한 세그먼트 크기를 선택하면 거의 캐시 미스 없이 연산을 진행할 수 있어, 큰 n에서는 세그먼트 체가 사실상 가장 빠른 방법이 됩니다. 일반 체로는 캐시 미스로 몇 배 느려질 상황에서도, 세그먼트 체는 캐시 히트율을 높여 꾸준한 성능을 발휘하기 때문입니다.

정리하면: 세그먼트 체는 n이 작을 때는 오히려 약간의 오버헤드가 있을 수 있지만, n이 커질수록 상대적으로 유리해지는 기법입니다. 특히 메모리가 한정된 환경이나 n이 매우 큰 경우 세그먼트 체는 유일한 해결책일 수 있으며, 이러한 맥락에서 최적화된 소수 라이브러리(primesieve 등)는 기본적으로 세그먼트 체를 채택하고 있습니다 (python - Prime number hard drive storage for very large primes - Sieve of Atkin - Stack Overflow).

선형 체(Linear Sieve)의 O(n) 성능 평가

**선형 체(Euler Sieve)**는 이론적으로 가장 효율적인 복잡도(O(n))를 가지지만, 앞서 언급한 바와 같이 실제 성능은 이론과 다를 수 있습니다. 선형 체는 매 합성수를 정확히 한 번만 지우도록 알고리즘을 구성한 것으로, 추가 자료구조로 최소 소인수 배열(lp[])을 유지하고, 소수 리스트를 관리하면서 진행합니다 (Linear Sieve - Algorithms for Competitive Programming) (Linear Sieve - Algorithms for Competitive Programming).

이 방식의 장점은 분명합니다: 불필요한 중복 제거 연산이 없으므로 이론상 최소한의 작업만 수행합니다. 그러나 단점도 몇 가지 있습니다:

• 상수 인자가 큼: 각 i에 대해 소수 리스트를 순회하며 배수를 지우기 때문에, 최악의 경우 (i * p_j <= n) 조건에서 소수 리스트의 상당 부분을 탐색해야 합니다 (Linear Sieve - Algorithms for Competitive Programming). 즉 이중 루프 구조인데, 비록 전체 복잡도는 선형으로 수렴하지만 루프 내 연산과 분기가 많습니다. 일반 체는 이중 루프이지만 내적 루프가 단순한 반면, 선형 체는 외적 이중 루프 구조로 구현되어 C 등의 언어에서도 분기 예측에 부담을 줍니다. 파이썬같이 루프 비용이 큰 언어에서는 오히려 더 불리합니다. 우리 실험에서도 선형 체 구현이 최적화된 에라토스테네스보다 느린 것으로 나타났습니다. 이는 이론적인 n log log n vs n의 미세한 차이보다는 구현 비용 차이 때문입니다 (Linear Sieve - Algorithms for Competitive Programming).
• 메모리 사용 증가: 앞서 메모리 비교에서 보았듯, 선형 체는 추가 배열(lp)과 소수 리스트를 유지해야 하므로 메모리를 더 씁니다 (Linear Sieve - Algorithms for Competitive Programming). 메모리 접근이 더 많아지고, 캐시 사용 측면에서도 불리할 수 있습니다.
• 복잡한 구현: 선형 체는 구현이 조금 더 복잡하여, 파이썬 등에서 최적화를 적용하기도 까다롭습니다. (예: 일반 체는 슬라이스로 배수 삭제가 가능하지만, 선형 체는 소수를 하나씩 처리하므로 그런 벡터화가 어렵습니다.)

그 결과, **선형 체는 이론과 달리 “모든 면에서 고전적 체보다 나을 것이 없다”**는 평가도 있습니다 (Linear Sieve - Algorithms for Competitive Programming). 특히 시간 면에서 세그먼트 체 등 최적화된 O(n log log n) 알고리즘보다 확실히 느리다는 보고가 있습니다 (Linear Sieve - Algorithms for Competitive Programming). 다만 선형 체는 각 수의 소인수 정보를 함께 얻을 수 있다는 부가 이익이 있어 특정 응용에 쓰일 가치가 있습니다 (Linear Sieve - Algorithms for Competitive Programming). 순수하게 소수 리스트만 구하는 목적이라면, 현실적으로 가장 빠른 알고리즘은 선형 체가 아닌 앞서 말한 세그먼트+비트 최적화된 체입니다.

기타 최적화 기법 및 이론적 배경

마지막으로, 위에서 다룬 내용 이외에 소수 생성 알고리즘에서 사용되는 기타 주요 최적화들을 간략히 언급합니다:

• 배수 지우기 시작점 최적화: 에라토스테네스 체 구현 시 소수 p의 배수를 지울 때 2p부터 시작하지 않고 p^2부터 시작하면 중복 작업을 줄일 수 있습니다. 이는 p < q < p^2인 소수 q들이 이미 p의 배수를 지웠기 때문입니다. 이런 개선은 알고리즘의 이론 복잡도에는 영향을 주지 않지만, 작은 최적화로 약 15% 가량 연산 감소 효과가 있습니다. 대부분의 “Optimized Sieve” 구현은 이 기법을 기본 적용하고 있습니다.
• 외부 메모리 대응: n이 너무 커서 메모리에 다 담기 어렵다면, 디스크에 블록을 저장하며 진행하는 방법이나, 아예 생성기(generator) 형태로 소수를 한 개씩 생산하는 알고리즘도 고려됩니다. 이러한 방법은 특수한 상황에서 쓰이며 일반적이지는 않습니다.
• 병렬화: 현대 컴퓨터의 멀티코어를 활용해 스레드 병렬화나 GPU 가속을 적용하면 실질 실행 시간을 더욱 줄일 수 있습니다. 예를 들어 세그먼트 체는 각 세그먼트를 독립적으로 처리할 수 있어 스레드로 병렬화하기 용이합니다. 적절히 구현하면 거의 선형에 가깝게 속도가 증가하여, 수십 억 범위의 소수도 수 초 내에 찾는 수준에 도달할 수 있습니다 (물론 이때도 이론 복잡도는 변하지 않습니다).
• 수학적 개선 알고리즘: 에라토스테네스 외에도 **아트킨의 체(Sieve of Atkin)**나 프리차드의 휠 체 등 이론적으로 더 나은 성능을 목표로 한 알고리즘들이 연구되었습니다. 예를 들어 아트킨의 체는 이론상 O(n)이라고 알려져 있고, 프리차드의 휠 체는 O(n / log log n)까지 개선된다고 하지만 (Pritchard’s Wheel Sieve | Programming Praxis) (Pritchard’s Wheel Sieve | Programming Praxis), 구현이 매우 복잡하고 상수 시간이 커서 실용적인 이득은 크지 않은 경우가 많습니다 (Prime Sieves - Graph All The Things) (Prime Sieves - Graph All The Things). 실제로 아트킨의 체와 에라토스테네스 체를 구현 비교한 결과 큰 n에서 성능이 비슷하거나 에라토스테네스 쪽이 유리한 것으로 나타났습니다 (Prime Sieves - Graph All The Things). 따라서 오늘날 가장 널리 쓰이는 소수 생성 알고리즘은 여전히 에라토스테네스 체이며, 대신 앞서 언급한 구현 최적화들(자료구조, 휠, 비트, 세그먼트, 병렬화)을 조합하여 성능을 극한까지 끌어올리는 방향으로 발전하고 있습니다.

종합 평가 및 결론: 가장 효율적인 방법은?

여러 가지 알고리즘을 이론 및 구현 측면에서 비교한 결과를 정리하면 다음과 같습니다:

• 이론적 복잡도만 놓고 보면 Linear Sieve가 O(n)으로 가장 효율적이지만, 실제 구현상의 상수 시간과 메모리 요인으로 인해 최적의 선택은 아닙니다.
• 실제 성능은 에라토스테네스 체를 얼마나 효율적으로 구현하느냐에 따라 좌우됩니다. 휠 최적화를 통해 불필요한 후보를 줄이고, 비트 배열로 메모리 사용을 최소화하며, 필요하면 세그먼트 기법으로 캐시 성능을 높이는 것이 핵심입니다. 특히 파이썬 환경에서는 numpy 나 bitarray를 사용하여 C 레벨에서 대량의 비트 연산을 수행하는 방법이 가장 빠릅니다.
• 가장 효율적인 방법은 결국 에라토스테네스 체의 궁극적 최적화 버전입니다. 예를 들면, *“짝수/소수5까지 휠 제거 + 비트 배열 사용 + 세그먼트 처리”*를 조합하면 거의 한계에 가까운 성능을 얻습니다. 이러한 접근은 메모리 접근 패턴이 최적화되고 불필요한 연산을 최대한 제거하여, 동일한 O(n log log n) 복잡도 내에서 상수를 극도로 줄인 구현이라 할 수 있습니다. 실제로 최신 소수 라이브러리들은 이처럼 다양한 기법을 조합하여 billions 단위 범위에서도 매우 빠르게 동작합니다.

결론적으로, 비트 배열 기반의 에라토스테네스 체 (필요에 따라 휠 및 세그먼트 최적화 포함)가 전반적으로 가장 효율적인 소수 생성 방법임을 확인할 수 있습니다. 이 방법은 시간과 메모리 측면 모두에서 균형이 우수하며, 일반적으로 다른 대안들을 압도하는 성능을 보여줍니다 (python - Fastest way to list all primes below N - Stack Overflow) (Linear Sieve - Algorithms for Competitive Programming). Linear Sieve와 같은 특수 알고리즘은 이론적 의미는 있지만, 실제 문제 해결에서는 잘 최적화된 에라토스테네스 체를 능가하기 어렵다는 것이 분석의 결론입니다. 고로 가장 효율적인 소수 판별 알고리즘으로는, **최적화된 에라토스테네스 체 (비트 배열 + 휠 + 세그먼트)**를 꼽을 수 있습니다. 이 방법을 통해 매우 큰 범위의 소수를도 상대적으로 짧은 시간 안에 찾아낼 수 있습니다.

참고 문헌 및 출처: 다양한 구현 기법과 최적화에 대한 분석은 Competitive Programming 알고리즘 자료 (Sieve of Eratosthenes - Algorithms for Competitive Programming) (Sieve of Eratosthenes - Algorithms for Competitive Programming) (Sieve of Eratosthenes - Algorithms for Competitive Programming), Wikipedia (Wheel factorization - Wikipedia), 그리고 Stack Overflow 토론 (c++ - How does segmentation improve the running time of Sieve of Eratosthenes? - Stack Overflow) (python - Fastest way to list all primes below N - Stack Overflow) 등을 기반으로 하였습니다. 이러한 자료들에서 공통적으로 강조하는 바는, _메모리 접근 패턴과 하드웨어 활용_이 소수 알고리즘의 실제 성능을 결정한다는 점입니다.

---

---

위 그래프는 다양한 소수 판별 알고리즘의 실행 시간을 Original Sieve(100%) 기준으로 비교한 것입니다.

• Original(기본 구현)이 가장 느리며(100%),
• Optimized(최적화된 에라토스테네스의 체)가 약 55%의 실행 시간으로 개선되었습니다.
• Bitwise는 비트 연산을 사용했지만 구현 오버헤드로 인해 예상보다 성능이 낮았습니다(261%).
• Array 구현은 리스트보다 약간 개선되었지만 큰 차이는 없었습니다(95%).
• Mod6(휠 6 최적화) 기법은 배수 소거량을 줄여 훨씬 빠른 성능을 보였습니다(36%).
• Wheel30(휠 30 최적화)은 Mod6보다 추가적인 최적화를 제공했지만, 상수 시간이 증가하여 중간 정도의 성능을 보였습니다(62%).
• Bitarray는 비트 배열을 활용하여 가장 빠른 성능을 보였으며, Original 대비 17% 수준의 실행 시간만 필요했습니다.
• Segmented(세그먼트 체)는 메모리 효율을 개선하였으나 실행 속도는 약간 손해를 보았습니다(83%).
• Linear(선형 체)는 O(n) 복잡도지만, 내부 연산 오버헤드로 인해 거의 Original과 비슷한 성능을 보였습니다(99%).

이 그래프를 바탕으로, 가장 빠른 방법은 Bitarray Sieve이며, 최적화된 Mod6 및 Wheel30도 상당히 좋은 성능을 발휘한다는 점을 확인할 수 있습니다. 🚀