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

== 구현 예시 ==
=== 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>

=== C++ ===
<syntaxhighlight lang="cpp">
/*
에라토스테네스의 체 (C++)

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

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

#include <iostream>
#include <vector>
#include <cmath>
#include <string>

static std::vector<int> sieve_of_eratosthenes(int n) {
    // n이 2보다 작으면 소수가 없다.
    if (n < 2) {
        return {};
    }

    // is_prime[i] == true  -> i는 소수 후보
    // is_prime[i] == false -> i는 합성수(또는 0/1)
    std::vector<bool> is_prime(static_cast<std::size_t>(n + 1), true);

    // 0과 1은 소수가 아니다.
    is_prime[0] = false;
    is_prime[1] = false;

    // 2부터 √n까지 확인한다.
    int limit = static_cast<int>(std::sqrt(static_cast<double>(n)));
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            // i*i 미만의 배수는 이미 더 작은 소수 단계에서 지워졌으므로 i*i부터 시작한다.
            long long start = 1LL * i * i;
            for (long long j = start; j <= n; j += i) {
                is_prime[static_cast<std::size_t>(j)] = false;
            }
        }
    }

    // 소수만 추출한다.
    std::vector<int> primes;
    primes.reserve(n / 10); // 대략적인 예약(정확하지 않아도 무방)

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (!(std::cin >> n)) {
        // 입력이 없으면 종료한다.
        return 0;
    }

    std::vector<int> primes = sieve_of_eratosthenes(n);

    // 공백으로 구분해 한 줄 출력한다.
    for (std::size_t i = 0; i < primes.size(); i++) {
        if (i > 0) {
            std::cout << ' ';
        }
        std::cout << primes[i];
    }
    std::cout << '\n';

    return 0;
}
</syntaxhighlight>

=== JavaScript ===
<syntaxhighlight lang="javascript">
/*
에라토스테네스의 체 (JavaScript / Node.js)

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

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

"use strict";

/**
 * 에라토스테네스의 체로 n 이하의 모든 소수를 구한다.
 *
 * @param {number} n - 상한 값
 * @returns {number[]} - 2 이상 n 이하의 소수 목록
 */
function sieveOfEratosthenes(n) {
  // n이 2보다 작으면 소수가 없다.
  if (n < 2) {
    return [];
  }

  // isPrime[i] === true  -> i는 소수 후보
  // isPrime[i] === false -> i는 합성수(또는 0/1)
  const isPrime = new Array(n + 1).fill(true);

  // 0과 1은 소수가 아니다.
  isPrime[0] = false;
  isPrime[1] = false;

  // 2부터 √n까지 확인한다.
  const limit = Math.floor(Math.sqrt(n));
  for (let i = 2; i <= limit; i++) {
    if (isPrime[i]) {
      // i*i 미만의 배수는 이미 더 작은 소수 단계에서 지워졌으므로 i*i부터 시작한다.
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }

  // 소수만 추출한다.
  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) {
      primes.push(i);
    }
  }

  return primes;
}

/**
 * 프로그램 진입점.
 * 표준 입력에서 N을 읽고, 소수 목록을 공백으로 구분해 출력한다.
 */
function main() {
  const fs = require("fs");

  const input = fs.readFileSync(0, "utf8").trim();
  if (input.length === 0) {
    // 입력이 비어 있으면 아무 것도 출력하지 않는다.
    return;
  }

  const n = Number(input);
  const primes = sieveOfEratosthenes(n);

  process.stdout.write(primes.join(" ") + "\n");
}

main();
</syntaxhighlight>