Sieve of Eratosthenes

Finds all primes up to n. Mark multiples of each prime as composite, starting from i² and iterating only up to √n.

Cilia

func sieveOfEratosthenes(Int n) -> Int[] {
    if n < 2 {
        return {}
    }

    Bool[] isPrime(n + 1, True)
    isPrime[0] = False
    isPrime[1] = False

    Int limit = isqrt(n)
    for i in 2..limit {
        if isPrime[i] {
            for j in i*i..n : i {
                isPrime[j] = False
            }
        }
    }

    Int[] primes
    primes.reserve(n / 10)
    for i in 2..n {
        if isPrime[i] {
            primes.append(i)
        }
    }

    return primes
}

C++

auto sieve_of_eratosthenes(int n) -> vector<int> {
    if (n < 2) {
        return {};
    }

    vector<bool> is_prime(n + 1, true);
    is_prime[0] = false;
    is_prime[1] = false;

    int limit = isqrt(n);
    for (int i = 2; i <= limit; ++i) {
        if (is_prime[i]) {
            for (int j = i*i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

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

    return primes;
}