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

=== Python ===
<syntaxhighlight lang="python">
"""
에라토스테네스의 체 (Python 3.x)

- 입력: 표준 입력으로 정수 N (N >= 0)
- 출력: 2 이상 N 이하의 모든 소수를 공백으로 구분하여 한 줄에 출력
        (소수가 없으면 빈 줄)

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

from __future__ import annotations


def sieve_of_eratosthenes(n: int) -> list[int]:
    """
    에라토스테네스의 체로 n 이하의 모든 소수를 구한다.

    Args:
        n (int): 상한 값

    Returns:
        list[int]: 2 이상 n 이하의 소수 목록
    """
    # n이 2보다 작으면 소수가 없다.
    if n < 2:
        return []

    # is_prime[i] == True  -> i는 소수 후보
    # is_prime[i] == False -> i는 합성수(또는 0/1)
    is_prime = [True] * (n + 1)

    # 0과 1은 소수가 아니므로 False로 표시한다.
    is_prime[0] = False
    is_prime[1] = False

    # 2부터 √n까지 확인한다.
    # i가 소수라면 i의 배수들을 합성수로 지운다.
    limit = int(n ** 0.5)
    for i in range(2, limit + 1):
        if is_prime[i]:
            # i*i 미만의 배수(2i, 3i, ..., (i-1)i)는
            # 더 작은 소수 단계에서 이미 지워졌으므로 i*i부터 시작한다.
            start = i * i
            step = i
            for j in range(start, n + 1, step):
                is_prime[j] = False

    # True로 남아 있는 인덱스만 소수이므로 리스트로 추출한다.
    primes: list[int] = []
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)

    return primes


def main() -> None:
    """
    프로그램 진입점.

    표준 입력에서 N을 읽고,
    n 이하의 소수를 공백으로 구분해 출력한다.
    """
    import sys

    data = sys.stdin.read().strip()
    if not data:
        # 입력이 비어 있으면 아무 것도 출력하지 않는다.
        return

    n = int(data)
    primes = sieve_of_eratosthenes(n)

    # 소수 목록을 한 줄로 출력한다.
    # 소수가 없으면 빈 줄이 출력된다.
    sys.stdout.write(" ".join(map(str, primes)) + "\n")


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