Sieve Of Eratosthenes

The Classic and Linear sieve!

So, I’ve just found out the O(n) sieve of Eratosthenes version after sticking with the classic O(n log log n) one for years. That’s why I would like to share it with you guys! If you’ve been using the classic sieve and thought it was optimal, well, there’s an alternative way.

Well, ikr — there are so many different sieve algorithms out there, but I never really explored them before, so ;-;

The Sieve of Eratosthenes is one of the most efficient algorithms to generate all prime numbers up to a given integer n (mainly in terms of ease of implementation and understanding, I know there are others like the Sieve of Atkin.). It works by iteratively marking the multiples of each prime number starting from 2. The two main implementations of this algorithm in this blog are:

• Classic Sieve of Eratosthenes (O(n log log n))
• Linear Sieve (O(n)) — Euler Sieve

Let’s go through both of them one by one.

Classic Sieve of Eratosthenes

The one we well familiar with

The classic sieve starts by assuming all numbers from 2 to n are prime. Then, for each prime p, it marks all of its multiples as composite (non-prime). This process continues up to sqrt(n), because any composite number x > sqrt(n) must have at least one factor ≤ sqrt(n), which would have already been marked.

Time Complexity Analysis

• We iterate through numbers up to sqrt(n), marking multiples in an O(n log log n) fashion.
• The reason for O(n log log n) complexity is that each number is affected by only a few primes, and the number of operations resembles the harmonic series, which sums up to O(n log log n).

C/C++

void classic_sieve(int n){
    vector<bool> ch(n+1, false);
    ch[2] = 1;
    for(int i=3; i<=n; i+=2) ch[i] = 1;
    for(int i=3; i<=sqrt(n); i++){
        if(!ch[i]) continue;
        for(int j=i*i; j<=n; j+=i){
            ch[j] = 0;
        }
    }
    for(int i=1; i<=n; i++){
        if(ch[i]) printf("%d ", i);
    }
    printf("\n");
    return;
}

Python

def classic_sieve(n):
    ch = [False] * (n + 1)
    ch[2] = True
    for i in range(3, n + 1, 2):
        ch[i] = True
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if not ch[i]:
            continue
        for j in range(i * i, n + 1, i):
            ch[j] = False
    print(*[i for i in range(1, n + 1) if ch[i]])

Linear Sieve of Eratosthenes (O(n))

optimizing the classic method

The linear sieve optimizes the classic method by ensuring that each number is marked only once by its smallest prime factor (LPF). Instead of iterating over all numbers up to sqrt(n), it maintains a list of prime numbers and efficiently marks multiples.

Time Complexity Analysis

• Unlike the classic sieve, every number is processed only once, leading to an optimal O(n) complexity.
• This is achieved using the lowest prime factor (LPF) method, which prevents redundant marking.

C/C++

void linear_sieve(int n){
    vector<int> pr; # Store primes
    vector<int> lp(n+1, 0); # Store lowest prime factor
    for(int i=2; i<=n; i++){
        if(lp[i] == 0){
            lp[i] = i;
            pr.push_back(i);
        }
        for(int j=0; j < pr.size() && pr[j] * i <= n; j++){
            lp[pr[j] * i] = pr[j];
            if(lp[i] == pr[j]) break;
        }
    }
    for(auto x : pr) printf("%d ", x);
    printf("\n");
    return;
}

Python

def linear_sieve(n):
    pr = []  # Store primes
    lp = [0] * (n + 1)  # Store lowest prime factor
    for i in range(2, n + 1):
        if lp[i] == 0:
            lp[i] = i
            pr.append(i)
        for p in pr:
            if p * i > n:
                break
            lp[p * i] = p
            if lp[i] == p:
                break
    print(*pr)

Additional Points

Time Complexity: Is the Linear Sieve Faster?

• The Sieve of Eratosthenes runs in O(nlog⁡log⁡n), while the Linear Sieve runs in O(n).
• Since loglogn grows very slowly, the speed improvement of the Linear Sieve is barely noticeable in practice.
• There is an Optimized versions of the Sieve of Eratosthenes, like the Segmented Sieve, are actually faster than the Linear Sieve.

Memory Usage: Is It More Efficient?

• The Sieve of Eratosthenes only needs one boolean array of size nn to mark prime numbers.
• The Linear Sieve needs two arrays:

lp[](Least Prime Factor) of size n.

pr[](List of primes) of size roughly nlognlogn.

• This makes the Linear Sieve less memory-efficient compared to the classic sieve.

The Hidden Benefit: Fast Prime Factorization

• The unique advantage of the Linear Sieve is that it precomputes prime factorizations.
• Using the lp[]lp[] array, we can quickly find the prime factorization of any number up to nn in O(log⁡n) time.

Feel free to correct me in the comments or let me know if I got anything wrong

Sources/Extra Reading:

How is the time complexity of Sieve of Eratosthenes is n*log(log(n))? - GeeksforGeeks

Sieve of Eratosthenes in 0(n) time complexity - GeeksforGeeks

Linear Sieve - Algorithms for Competitive Programming