🐨세그먼트-시브 segmented-sieve

세그먼트 시브(Segmented Sieve) 알고리즘 설명

0. 기본 개념: 에라토스테네스의 체 복습

에라토스테네스의 체는 소수를 빠르게 찾는 유명한 알고리즘이다. 다음은 간단한 구현 예시이다:

def basic_sieve(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 [i for i in range(n + 1) if is_prime[i]]

# 실행 예시
print(basic_sieve(30))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

이 방식은 간단하지만, 큰 수를 처리할 때 메모리 문제가 발생할 수 있다. 예를 들어, $n=10^8$일 때 필요한 메모리를 확인해보자:

import sys
n = 10**8
memory_usage = sys.getsizeof([True] * (n + 1)) / (1024 * 1024)  # MB 단위
print(f"필요한 메모리: {memory_usage:.2f}MB")  # 약 95MB

위와 같이 큰 수를 다룰 때 메모리 사용량이 커지기 때문에, 효율적인 대안이 필요하다. 그 대안이 세그먼트 시브이다.

1. 세그먼트 시브의 필요성

세그먼트 시브는 큰 범위의 소수를 찾을 때 메모리 사용을 절감하기 위해 사용되는 방법이다. 일반적인 에라토스테네스의 체는 모든 숫자에 대한 정보를 저장해야 하기 때문에, 매우 큰 수를 처리할 때는 메모리가 부족하게 된다. 이를 해결하기 위해 세그먼트 시브는 큰 범위를 작은 구간으로 나누어 처리함으로써 메모리 사용을 줄인다.

1.1 문제 상황 예시

# 큰 범위의 소수 찾기 시도
def find_large_primes():
    n = 10**9  # 10억
    try:
        primes = basic_sieve(n)  # MemoryError 발생 가능
    except MemoryError:
        print("메모리 부족 발생!")

$n=10^9$인 경우에는 메모리 부족으로 인해 일반적인 에라토스테네스의 체를 사용할 수 없다. 이런 상황에서 세그먼트 시브를 활용하면 메모리 사용량을 크게 줄일 수 있다.

2. 세그먼트 시브 단계별 구현

세그먼트 시브 알고리즘은 다음과 같은 단계로 이루어진다.

2.1 기초 소수 찾기

세그먼트 시브는 구간별로 소수를 찾기 때문에, 먼저 $$\sqrt{n}$까지의 소수를 찾아야 한다. 이를 "기초 소수"라고 한다. 이 기초 소수들은 이후 각 구간에서 배수를 제거하는 데 사용된다.

def find_base_primes(limit):
    """√N까지의 기초 소수 찾기
    """
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    
    return [i for i in range(limit + 1) if is_prime[i]]

# 실행 예시
base_primes = find_base_primes(20)
print(f"기초 소수: {base_primes}")  # [2, 3, 5, 7, 11, 13, 17, 19]

2.2 세그먼트 처리

기초 소수를 사용해 큰 범위를 작은 구간으로 나눠 소수를 찾는다. 이를 "세그먼트 처리"라고 한다. 각 구간에 대해 기초 소수들의 배수를 제거함으로써 소수를 찾는다.

def process_segment(base_primes, start, end):
    """그 구간의 소수 찾기
    """
    # 1. 구간 초기화
    size = end - start + 1
    segment = [True] * size
    
    # 2. 기초 소수의 배수 제거
    for prime in base_primes:
        # 구간 내 첫 배수 찾기
        first_multiple = ((start + prime - 1) // prime) * prime
        if first_multiple < start:
            first_multiple += prime
            
        # 배수 제거
        for multiple in range(first_multiple, end + 1, prime):
            segment[multiple - start] = False
    
    # 3. 남은 소수 반환
    return [i + start for i in range(size) if segment[i]]

# 실행 예시
segment_primes = process_segment([2, 3, 5], 30, 50)
print(f"30-50 구간의 소수: {segment_primes}")

이 단계에서는 각 구간의 시작점부터 끝점까지의 숫자들에 대해, 기초 소수의 배수들을 모두 지워나가면서 소수를 남긴다.

구현할 때 중요한 점은 세그먼테이션 오류를 피하기 위해 범위 내 소수의 첫 배수를 찾을 때 올림값을 사용해야 한다

예를 들어 설명하면:

1. L = 17, 소수 P = 2인 경우를 생각해봅시다.
2. 첫 배수를 찾을 때 L/P를 계산합니다:
   • 17 ÷ 2 = 8.5
3. 이때 두 가지 선택이 있습니다:
   • 내림(floor): 8
   • 올림(ceil): 9
4. 각각의 경우를 살펴보면:
   • 내림값(8)을 사용할 경우:
     • 8 × 2 = 16 (첫 배수)
     • 16은 L(17)보다 작음
     • 배열 인덱스: 16 - 17 = -1 → 배열 범위 벗어남 (세그멘테이션 오류 발생!)
   • 올림값(9)을 사용할 경우:
     • 9 × 2 = 18 (첫 배수)
     • 18은 L(17)보다 큼
     • 배열 인덱스: 18 - 17 = 1 → 안전!

따라서 올림값을 사용하면 항상 L보다 크거나 같은 첫 배수를 찾을 수 있어 배열 범위를 벗어나는 문제를 방지할 수 있습니다. 이것이 세그먼테이션 오류를 피하는 핵심 구현 포인트입니다.

2.3 전체 알고리즘 구현

세그먼트 시브 알고리즘 전체를 구현해보자. 먼저 기초 소수를 찾은 후, 큰 범위를 여러 구간으로 나누어 처리한다.

def segmented_sieve(n, segment_size=1000):
    # 1. 기초 소수 찾기
    limit = int(n ** 0.5) + 1
    base_primes = find_base_primes(limit)
    result = [p for p in base_primes]  # 기초 소수 저장
    
    # 2. 구간별 처리
    for start in range(limit + 1, n + 1, segment_size):
        end = min(start + segment_size - 1, n)
        segment_primes = process_segment(base_primes, start, end)
        result.extend(segment_primes)
    
    return result

# 실행 예시와 결과 분석
n = 100
primes = segmented_sieve(n)
print(f"찾은 소수 개수: {len(primes)}")
print(f"마지막 5개 소수: {primes[-5:]}")

위의 전체 알고리즘에서는 먼저 기초 소수를 찾고, 그 다음 $n$까지의 범위를 segment_size 단위로 나누어 각 구간에서 소수를 찾는다. 이렇게 하면 큰 수를 다룰 때도 메모리 사용량을 최소화하면서 효율적으로 소수를 찾을 수 있다.

3. 성능 검증

세그먼트 시브는 메모리를 효율적으로 사용하기 때문에 큰 수의 소수를 찾는 데 매우 유리하다. 실행 시간 비교를 통해 성능을 검증해보자.

3.1 실행 시간 비교

import time

def compare_performance(n):
    # 기본 체 시간 측정
    start = time.time()
    basic_primes = basic_sieve(n)
    basic_time = time.time() - start
    
    # 세그먼트 체 시간 측정
    start = time.time()
    segment_primes = segmented_sieve(n)
    segment_time = time.time() - start
    
    print(f"기본 체 실행 시간: {basic_time:.3f}초")
    print(f"세그먼트 체 실행 시간: {segment_time:.3f}초")

# 실행
compare_performance(10**6)

이 비교를 통해 세그먼트 시브가 큰 범위의 소수를 찾을 때 얼마나 효율적인지 알 수 있다. 메모리를 아끼면서도 계산 속도를 어느 정도 유지할 수 있는 것이 장점이다.

4. 실전 문제 해결

4.1 구간 소수 찾기

세그먼트 시브는 특정 범위 내에서 소수를 찾는 데도 유용하다. 다음은 주어진 범위에서 소수를 찾는 예시이다.

def find_primes_in_range(start, end):
    """주어진 구간의 소수만 찾기"""
    limit = int(end ** 0.5) + 1
    base_primes = find_base_primes(limit)
    return process_segment(base_primes, start, end)

# 예시: 1000-2000 사이의 소수
range_primes = find_primes_in_range(1000, 2000)
print(f"1000-2000 사이 첫 5개 소수: {range_primes[:5]}")

4.2 골드바흐 파티션 찾기

다음은 골드바흐의 추측을 사용하여 주어진 짝수를 두 소수의 합으로 나타내는 예시이다.

def find_goldbach_partition(n):
    """짝수를 두 소수의 합으로 표현"""
    primes = set(segmented_sieve(n))
    for p in primes:
        if (n - p) in primes:
            return p, n - p
    return None

# 예시
n = 100
result = find_goldbach_partition(n)
print(f"{n} = {result[0]} + {result[1]}")

5. 핵심 정리

1. 에라토스테네스의 체를 최적화-특히 숫자는 매우 크지만 범위(L부터 R까지)는 상대적으로 작을 때 효과적입니다.
2. 일반 체는 $O(R)$의 공간 복잡도, 세그먼트 체는 $O(√R + (R-L))$의 공간만 필요=메모리 효율성(예: 2TB vs 2MB)
3. 알고리즘 4단계
   - 일반 체로 √R까지의 모든 소수 찾기
   - (R-L+1) 크기의 배열 생성 
   - 범위 내에서 찾은 소수들의 배수 표시
   - 표시되지 않은 남은 숫자들을 소수로 수집

4. 구현할 때 중요한 점은 세그먼테이션 오류를 피하기 위해 범위 내 소수의 첫 배수를 찾을 때 올림값을 사용해야 한다는 것입니다.

5. 시간 복잡도는 O(√R log log √R + (R-L) * √R/log(√R))로, 10^12부터 (10^12 + 10^6)까지와 같은 큰 범위에서 소수를 찾는 시나리오에서 효율적입니다.

1. 메모리 효율성: 세그먼트 시브는 O(√n)의 메모리만 사용하여 큰 수의 소수를 찾을 수 있다.
2. 캐시 효율성: 작은 구간 단위로 처리하기 때문에 캐시 효율이 좋다.
3. 구현 복잡도: 기본 에라토스테네스의 체보다 복잡하지만, 큰 수를 처리할 수 있는 장점이 있다.
4. 적용 범위: 매우 큰 수 범위의 소수 찾기에 효과적이다.

https://www.scaler.in/segmented-sieve/

Segmented Sieve - Scaler Blog