Prime¶

Sieve of Eratosthenes¶

Algorithm (Sieve of Eratosthenes)

To find all prime numbers up to any given limit \(N\), the Sieve of Eratosthenes is an ancient algorithm based on the fact that any multiplication of integer \(x\) is not prime. The algorithm is to scan each integer \(x_i\) within the limit \(N\) starting at \(2\) and "erase" \(\{2x_i, 3x_i, \cdots, ⌊N/x_i⌋ * x_i\}\). Note that when an integer \(x_j\) is scanned but not marked, we know \(x_j\) is a prime. We can proof this by contradiction easily.

Code:

void primes(int n){
    memset(v,0,sizeof(v));
    for(int i=2;<=n;i++){
        if(v[i]) continue;
        cout<<i<<endl;
        for(int j=i;j<=n/i;j++)
            v[i*j]=1;
    }
}

The time complexity of Sieve of Eratosthenes is \(\mathcal{O}(\sum_{\text{prime} \; p \le N}{\frac{N}{p}}) = \mathcal{O}(N\log\log N)\).

Wikipedia ↩