구현

이 장에서는 에라토스테네스의 체, 확장 유클리드 호제법, 모듈러 역원, 빠른 거듭제곱을 하나의 Python 모듈로 구현하고 줄 단위로 설명합니다. 이어서 가장 자주 쓰는 체를 C++, Java, TypeScript로 똑같이 옮깁니다.

Python 구현

def sieve(n: int) -> list[int]:
    """n 이하의 소수를 오름차순으로 돌려준다."""
    if n < 2:
        return []
    is_prime = bytearray([1]) * (n + 1)
    is_prime[0] = is_prime[1] = 0
    i = 2
    while i * i <= n:
        if is_prime[i]:
            count = (n - i * i) // i + 1
            is_prime[i * i :: i] = bytes(count)
        i += 1
    return [k for k in range(n + 1) if is_prime[k]]


def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """(g, x, y)를 돌려준다. a * x + b * y == g == gcd(a, b)"""
    old_r, r = a, b
    old_x, x = 1, 0
    old_y, y = 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y
    return old_r, old_x, old_y


def mod_inverse(a: int, m: int) -> int:
    """a * x % m == 1 인 x (0 <= x < m). 서로소가 아니면 ValueError"""
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError(f"{a} has no inverse modulo {m}")
    return x % m


def mod_pow(base: int, exp: int, mod: int) -> int:
    """base ** exp % mod 를 O(log exp) 번의 곱셈으로 계산한다."""
    result = 1 % mod
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result


if __name__ == "__main__":
    print(sieve(30))                  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    print(extended_gcd(240, 46))      # (2, -9, 47)
    print(mod_inverse(3, 7))          # 5
    print(mod_pow(3, 13, 7))          # 3
    print(mod_pow(2, 10**18, 10**9 + 7) == pow(2, 10**18, 10**9 + 7))  # True

줄 단위 설명

sieve

• bytearray([1]) * (n + 1)은 칸마다 1바이트만 쓰는 배열입니다. [True] * (n + 1) 리스트보다 메모리가 훨씬 적습니다(리스트는 칸마다 8바이트 포인터).
• 0과 1은 소수가 아니므로 먼저 0으로 표시합니다.
• 바깥 반복은 i * i <= n인 동안만 돕니다. √n보다 큰 합성수는 반드시 √n 이하의 소인수를 가지므로 이미 지워졌습니다.
• is_prime[i * i :: i] = bytes(count)는 i × i부터 i 간격의 칸을 한 번에 0으로 바꾸는 슬라이스 대입입니다. Python 반복문으로 하나씩 지우는 것보다 몇 배 빠릅니다. count는 그 슬라이스의 길이와 정확히 같아야 합니다.
• 마지막 줄은 1로 남은 칸의 번호를 모아 소수 목록을 만듭니다.

extended_gcd

• (old_r, r)은 유클리드 호제법의 두 나머지이고, (old_x, x), (old_y, y)는 각 나머지를 a × x + b × y로 표현하는 계수입니다.
• 처음에는 a = a × 1 + b × 0, b = a × 0 + b × 1이므로 (1, 0), (0, 1)에서 시작합니다.
• 반복마다 몫 q를 구하고 세 쌍을 같은 규칙 새 값 = 이전 값 - q × 현재 값으로 갱신합니다. 튜플 대입이라 임시 변수가 필요 없습니다.
• 재귀 대신 반복을 쓰므로 아주 큰 수에서도 재귀 깊이 제한에 걸리지 않습니다.

mod_inverse

• a % m으로 먼저 줄이면 음수 a도 처리됩니다.
• g != 1이면 서로소가 아니므로 역원이 없습니다. 조용히 틀린 값을 돌려주는 대신 예외를 던집니다.
• x는 음수일 수 있으므로 x % m으로 0 이상 m 미만에 맞춥니다.

mod_pow

• result = 1 % mod는 mod == 1일 때 결과를 0으로 맞추기 위한 처리입니다.
• exp & 1로 맨 아래 비트를 보고, 1이면 지금의 base를 결과에 곱합니다.
• base를 제곱하고 exp를 오른쪽으로 한 비트 밀어 다음 자리로 넘어갑니다.
• Python 정수는 크기 제한이 없어서 오버플로는 없지만, 매번 % mod를 취해야 숫자가 커지지 않고 빠릅니다. 실제 코드에서는 내장 pow(base, exp, mod)를 쓰는 것이 가장 빠릅니다.

체를 C++로

C++에서는 vector<bool>이 비트 단위로 저장되어 메모리가 8분의 1로 줄어듭니다. i * i가 int 범위를 넘지 않도록 long long을 씁니다.

#include <iostream>
#include <vector>

std::vector<int> sieve(int n) {
    std::vector<int> primes;
    if (n < 2) return primes;
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (long long i = 2; i * i <= n; ++i) {
        if (!is_prime[i]) continue;
        for (long long j = i * i; j <= n; j += i) is_prime[j] = false;
    }
    for (int k = 2; k <= n; ++k)
        if (is_prime[k]) primes.push_back(k);
    return primes;
}

int main() {
    for (int p : sieve(30)) std::cout << p << ' ';
    std::cout << '\n';  // 2 3 5 7 11 13 17 19 23 29
}

체를 Java로

Java의 boolean[]은 기본값이 false이므로 "합성수인가"를 저장하면 초기화가 필요 없습니다. 여기서도 i * i의 오버플로를 피하려고 long으로 셉니다.

import java.util.ArrayList;
import java.util.List;

public class Sieve {
    static List<Integer> sieve(int n) {
        List<Integer> primes = new ArrayList<>();
        if (n < 2) return primes;
        boolean[] composite = new boolean[n + 1];
        for (long i = 2; i * i <= n; i++) {
            if (composite[(int) i]) continue;
            for (long j = i * i; j <= n; j += i) composite[(int) j] = true;
        }
        for (int k = 2; k <= n; k++)
            if (!composite[k]) primes.add(k);
        return primes;
    }

    public static void main(String[] args) {
        System.out.println(sieve(30)); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    }
}

체를 TypeScript로

Uint8Array는 칸마다 1바이트를 쓰는 고정 길이 배열이라 일반 배열보다 빠르고 가볍습니다. JavaScript의 number는 2^53까지 정수를 정확히 표현하므로 체의 범위에서는 오버플로 걱정이 없습니다.

export function sieve(n: number): number[] {
  if (n < 2) return [];
  const isPrime = new Uint8Array(n + 1).fill(1);
  isPrime[0] = 0;
  isPrime[1] = 0;
  for (let i = 2; i * i <= n; i++) {
    if (!isPrime[i]) continue;
    for (let j = i * i; j <= n; j += i) isPrime[j] = 0;
  }
  const primes: number[] = [];
  for (let k = 2; k <= n; k++) if (isPrime[k]) primes.push(k);
  return primes;
}

console.log(sieve(30).join(" ")); // 2 3 5 7 11 13 17 19 23 29

정리

네 언어의 체는 모두 같은 구조입니다. 0과 1을 지우고, i × i ≤ n인 소수 i마다 i × i부터 배수를 지운 뒤, 남은 칸을 모읍니다. 차이는 메모리 표현(bytearray, vector<bool>, boolean[], Uint8Array)과 i × i 오버플로를 막는 방식뿐입니다. 확장 유클리드와 빠른 거듭제곱은 C++과 Java에서 곱셈 오버플로를 조심해야 하는데, 이 내용은 실무 활용 장에서 자세히 다룹니다.