Sieve of Eratosthenes

Cilia

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

    Bool[] isPrime(n + 1, true)
    isPrime[0] = false
    isPrime[1] = false

    Int limit = Int(sqrt(n))
    for i in 2..limit {
        if !isPrime[i] {
            continue
        }
        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.pushBack(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 = static_cast<int>(sqrt(n));
    for (int i = 2; i <= limit; ++i) {
        if (!is_prime[i]) {
            continue;
        }
        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;
}