에라토스테네스의 체 편집하기 (부분)

=== 소인수분해 ===
에라토스테네스의 체를 변형하면 '''모든 수의 소인수분해'''를 빠르게 할 수 있다.

각 수에 대해 "가장 작은 소인수"를 저장해두면, <math>O(\log N)</math> 시간에 소인수분해가 가능하다.

<syntaxhighlight lang="python">
"""
Smallest Prime Factor(SPF)를 저장하는 체 + 빠른 소인수분해 (Python 3.x)

- sieve_with_spf(n): 2..n 범위에 대해 각 수의 최소 소인수(spf)를 계산한다.
- factorize(x, spf): spf를 이용해 x를 소인수분해하여 소인수 목록(중복 포함)을 반환한다.

이 코드는 "생략 없이" 실행 가능한 완전한 예시를 제공한다.
"""

from __future__ import annotations


def sieve_with_spf(n: int) -> list[int]:
    """
    0..n 범위에서 각 정수의 최소 소인수(SPF: Smallest Prime Factor)를 저장한다.

    spf[x]는 x의 최소 소인수이며,
    소수 p에 대해서는 spf[p] == p가 된다.

    Args:
        n (int): 상한 값

    Returns:
        list[int]: spf 배열 (길이 n+1)
    """
    # spf[i]를 i로 초기화한다.
    # 이후 합성수에 대해서만 더 작은 소인수로 갱신한다.
    spf = list(range(n + 1))

    if n >= 0:
        spf[0] = 0
    if n >= 1:
        spf[1] = 1

    limit = int(n ** 0.5)
    for i in range(2, limit + 1):
        # spf[i] == i 이면 i는 소수이다.
        if spf[i] == i:
            # i*i부터 시작하는 이유:
            # i의 더 작은 배수들은 이미 더 작은 소수 단계에서 처리되었기 때문이다.
            start = i * i
            for j in range(start, n + 1, i):
                # 아직 최소 소인수가 갱신되지 않은 경우에만 i로 설정한다.
                if spf[j] == j:
                    spf[j] = i

    return spf


def factorize(x: int, spf: list[int]) -> list[int]:
    """
    spf를 사용하여 x를 소인수분해한다.
    각 단계에서 x를 spf[x]로 나누므로 시간은 대략 O(log x) 수준이다.

    Args:
        x (int): 소인수분해할 정수 (x >= 1)
        spf (list[int]): sieve_with_spf로 만든 최소 소인수 배열

    Returns:
        list[int]: 소인수 목록(중복 포함)
    """
    factors: list[int] = []
    while x > 1:
        p = spf[x]
        factors.append(p)
        x //= p
    return factors


def main() -> None:
    """
    예시 실행:
    - 100까지 spf를 만든 뒤 60을 소인수분해한다.
    """
    spf = sieve_with_spf(100)
    print(factorize(60, spf))  # [2, 2, 3, 5]


if __name__ == "__main__":
    main()
</syntaxhighlight>