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

=== 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>