← all categories

Sieve a924f4ae

Sieve of Eratosthenes. Returns isPrime[0..n] and the ascending list of primes <= n.

Time: O(n \log\log n). tested

content/math/sieve.h

pair<vector<bool>, vector<int>> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    if (n >= 0) isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;
    for (int i = 2; (ll)i * i <= n; i++)
        if (isPrime[i])
            for (int j = i * i; j <= n; j += i) isPrime[j] = false;

    vector<int> primes;
    for (int i = 2; i <= n; i++) if (isPrime[i]) primes.push_back(i);
    return {isPrime, primes};
}