Sieve of Eratosthenes

The Sieve of Eratosthenes is a classic method for efficiently finding prime numbers up to a given limit, crucial in cryptography for securing data like credit card numbers. This ancient algorithm sieves out non-prime numbers, leaving behind the primes. By understanding this algorithm, we unlock a powerful tool for various mathematical applications, from fraction conversion to encryption. Ready to delve into the efficient world of prime number discovery? Let’s dive in!

Scope

• This article tells about the working of the Sieve of Eratosthenes.
• Optimizations of Sieve of Eratosthenes.
• Implementation of Sieve of Eratosthenes.
• Complexity of Sieve of Eratosthenes.

What is Sieve of Eratosthenes?

As mentioned above, it is an algorithm used for finding all the prime numbers in a given range from 1 to a given n, the number till where you want to find the primes.

What is the traditional method of finding primes though? Well, say you want to find all the prime numbers till 50, you might take every number from 1 to 50 into consideration to check if it is a prime. If the current number is a prime, then you add it to the result. Taking every number into consideration, and then finding its factors to check if it is a prime is definitely a cumbersome process.

Let’s see how the Sieve algorithm makes the process much easier.

Working of Sieve of Eratosthenes

In this algorithm, we start with the number 2, and iteratively mark the multiples of each prime number as composite (= not prime). That way, we know which numbers are primes, and which numbers aren’t (as they will be marked as not prime). For now, let’s not go into the code, let’s just observe the algorithm.

Here are the steps that we will follow :

1. List out all integers starting from 2 till n
2. Declare a variable p, that stores the value of the current prime number and initialize it to 2.
3. Cross out all the multiples of the current variable p - 2p, 3p, 4p etc.
4. Next step is to find the next smallest number that isn’t crossed out as it is definitely a prime, and store it in p. We already crossed out the multiples of p, so all the remaining numbers that have not been crossed out, definitely do not have p as a factor. So the next smallest number after p, too, does not have p as a factor and hence is prime, just like p. If there is no such number, then stop. Since we started off with p = 2, the next non-crossed number is 3, so now p = 3.
5. Repeat from step 3
6. All the unmarked numbers remaining are the prime numbers in the range 1- n.

Example of Sieve of Eratosthenes

Let’s find out all the prime numbers from 1 - 20 using the above method.

First step is to list out all the numbers.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

We start with p = 2, and cancel out all the numbers that are multiples of p.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

We have now cancelled out all the numbers that are multiples of p, and reached the end of the list. We now increment p, to the next smallest unmarked number. p = 3.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The next smallest unmarked number is 5, p = 5. We can see that all the multiples of 5 have already been marked. Another observation to make here is that we need not move any further to check for p = 7, p = 11 etc, they are already marked! This means that we have successfully crossed out all the composite ( non-prime) numbers, and all the unmarked numbers are clearly primes. This list of primes is our final result.

Let’s take another example and run our algorithm on it. This time, we’ll take n to be a larger number, say 50.

Just like before, let’s start with the number two, and cancel out all the multiples of 2.

Do you see how the numbers that we have to check for primes have reduced to almost half?

We now start crossing out the multiples of the next un crossed number, that is 3.

The same way, we cross all multiples of 5.

The next number that we have to check and cross is 7, and it is the last number. Why? If you observe, after 7, like in our previous example, the next number that we will check will be 11, and all the multiples of 11 have already been crossed out!

Whatever numbers that now remain uncrossed in our table, are the prime numbers between 1 and 50.

Now that we have understood the complete Sieve of Eratosthenes, let’s take a look at some code while reiterating the algorithm.

Code for Sieve of Eratosthenes

Here are the Effecient code for Sieve of Eratosthenes given below:

C++

#include <bits/stdc++.h>

using namespace std;

vector<int> Sieve(int n){
    vector<int> primes;
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p <= n; p++){
        if (prime[p] == true){
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    for (int p = 2; p <= n; p++)
        if (prime[p])
            primes.push_back(p);

    return primes;
}

Python :

def SieveOfEratosthenes(n: int) -> [int]:
    primes = []
    prime_bool = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
        if (prime_bool[p] == True):
            for i in range(p * p, n+1, p):
                prime_bool[i] = False
        p += 1
    for p in range(2, n+1):
        if prime_bool[p]:
            primes.append(p)
    return primes

Take a look at some Java code for reference :

Java

public static ArrayList<Integer> SieveOfEratosthenes(int n){
    ArrayList<Integer> primes = new ArrayList<>();
    boolean is_prime[] = new boolean[n+1];
    for (int i = 0; i <= n; i++)
        is_prime[i] = true;

    for (int p = 2; p * p <= n; p++){
        if (is_prime[p] == true){
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }
    for (int i = 2; i <= n; i++){
        if (is_prime[i] == true)
            primes.add(i);
    }
    return primes;
}

C

using System;

namespace prime {

    public static int[] SieveOfEratosthenes(int n){
        bool[] is_prime = new bool[n + 1];
        int[] primes = new int[] {}; 

        for (int i = 0; i < n; i++)
            is_prime[i] = true;

        for (int p = 2; p * p <= n; p++){
            if (is_prime[p] == true){
                for (int i = p * p; i <= n; i += p)
                    is_prime[i] = false;
            }
        }
        for (int i = 2; i <= n; i++){
            if (is_prime[i] == true)
                primes.add(prime[i]);
        }
        return primes;
    }

}

JavaScript

<script>

function SimpleSieve(n){
    is_prime = Array.from({length: n+1}, (_, i) => true);

    for (p = 2; p * p <= n; p++){
        if (is_prime[p] == true){
            for (i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }

    for (i = 2; i <= n; i++){
        if (is_prime[i] == true)
            document.write(i + " ");
    }
}

</script>

Php

<?php
function SieveOfEratosthenes($n){
    $is_prime = array_fill(0, $n + 1, true);
    for ($p = 2; $p * $p <= $n; $p++){
        if ($is_prime[$p] == true){
            for ($i = $p * $p; $i <= $n; $i += $p)
                $is_prime[$i] = false;
        }
    }

    for ($p = 2; $p <= $n; $p++){
        if ($is_prime[$p])
            echo $p." ";
    }
}
?>

Sieve of Eratosthenes – Time Complexity

The time complexity of the Sieve of Eratosthenes algorithm is O(nlog log n). How? Let’s analyze it!

To go further, let’s take a number n, so that we can find all the prime numbers between 1 and n. According to the simple Sieve algorithm, we must cross out the multiples of every prime number we discover starting from 2.

First things first, we are assuming that the time complexity of marking any number as composite (not prime) is constant, i.e. O(1). So if we calculate the number of times the loop runs, we can say it is :
n / 2 + n / 3 + n / 5 + n / 7 + ... p

Here in the above pattern, n/2 = all the numbers in range 1 - n divisible by 2, n/3 = all the numbers in range 1 - n divisible by 3 and so on till the last prime number in the range 1 - n that is p. Summing up all the multiples of the prime numbers is the total number of times the loop runs.

From this above equation, we can take 'n' common.

n * (1 / 2 + 1 / 3 + 1 / 5 + 1 / 7 + ... p)

It’s a harmonic progression of the primes and this is the result of the harmonic progression for the sum of primes.

Once we place this back to our original equation, we get:

$$
O(n * log(log(n))
$$

Conclusion

• The simple sieve of eratosthenes is an algorithm that is used to find prime numbers in the range 1 to a given n.
• In the sieve of Eratosthenes algorithm, we maintain a boolean vector of numbers from 1 - n, and mark composite numbers as False.
  • This is done by taking the smallest numbers starting from 2, and then marking it’s multiples as False (not prime) and so on.
• Time complexity of the simple sieve of Eratosthenes is $$ O(n*log(log(n))) $$
• The space complexity of the Simple Sieve algorithm is O(n) and for segmented sieve reduces it to O(sqrt(n)).
• The sieve algorithm is used in number theory and very commonly in cryptography.