Sieve of Eratosthenes Algorithm: Python, C++ Example

By : Alyssa Walker Alyssa Walker
Hours Updated

The Sieve of Eratosthenes is the simplest prime number sieve. It is a Prime number algorithm to search all the prime numbers in a given limit. There are several prime number sieves. For example- the Sieve of Eratosthenes, Sieve of Atkin, Sieve of Sundaram, etc.

The word “sieve” means a utensil that filters substances. Thus, the sieve algorithm in Python and other languages refers to an algorithm to filter out prime numbers.

This algorithm filters out the prime number in an iterative approach. The filtering process starts with the smallest prime number. A Prime is a natural number that is greater than 1 and has only two divisors, viz., 1 and the number itself. The numbers that are not primes are called composite numbers.

In the sieve of the Eratosthenes method, a small prime number is selected first, and all the multiples of it get filtered out. The process runs on a loop in a given range.

For example:

Let’s take the number range from 2 to 10.

Sieve of Eratosthenes Algorithm

After applying the Sieve of Eratosthenes, it will produce the list of prime numbers 2, 3, 5, 7

Sieve of Eratosthenes Algorithm

Algorithm Sieve of Eratosthenes

Here is the algorithm for the Sieve of Eratosthenes:

Step 1) Create a list of numbers from 2 to the given range n. We start with 2 as it is the smallest and first prime number.

Step 2) Select the smallest number on the list, x (initially x equals 2), traverse through the list, and filter the corresponding composite numbers by marking all the multiples of the selected numbers.

Step 3) Then choose the next prime or the smallest unmarked number on the list and repeat step 2.

Step 4) Repeat the previous step until the value of x should be lesser than or equal to the square root of n (x<=Algorithm Sieve of Eratosthenes).

Note: The mathematical reasoning is quite simple. The number range n can be factorized as-

n=a*b

Again, n =Algorithm Sieve of Eratosthenes*Algorithm Sieve of Eratosthenes

= (factor smaller than Algorithm Sieve of Eratosthenes) * (factor larger than Sieve of Eratosthenes Algorithm)

So at least one of the prime factors or both must be <=Algorithm Sieve of Eratosthenes. Thus, traversing to Algorithm Sieve of Eratosthenes will be enough.

Step 5) After those four steps, the remaining unmarked numbers would be all the primes on that given range n.

Example:

Let’s take an example and see how it works.

For this example, we will find the list of prime numbers from 2 to 25. So, n=25.

Step 1) In the first step, we will take a list of numbers from 2 to 25 as we selected n=25.

Algorithm Sieve of Eratosthenes

Step 2) Then we select the smallest number on the list, x. Initially x=2 as it is the smallest prime number. Then we traverse through the list and mark the multiples of 2.

The multiples of 2 for the given value of n is: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Sieve of Eratosthenes Algorithm

Note: Blue color denotes the selected number, and pink color denotes the eliminated multiples

Step 3) Then we choose the next smallest unmarked number, which is 3, and repeat the last step by marking the multiples of 3.

Sieve of Eratosthenes Algorithm

Step 4) We repeat step 3 in the same way until x=Sieve of Eratosthenes Algorithm or 5.

Sieve of Eratosthenes Algorithm

Step 5) The remaining non-marked numbers would be the prime numbers from 2 to 25.

Sieve of Eratosthenes Algorithm

Pseudo-Code

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Sieve of Eratosthenes C/C++ code Example

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    } 
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

Output:

2 3 5 7 11 13 17 19 23

Sieve of Eratosthenes Python Program Example

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Output:

2
3
5
7
11
13
17
19
23

Segmented Sieve

We have seen that the Sieve of Eratosthenes is required to run a loop through the whole number range. Thus, it needs O(n) memory space to store the numbers. The situation becomes complicated when we try to find primes in a huge range. It is not feasible to allocate such a large memory space for a bigger n.

The algorithm can be optimized by introducing some new features. The idea is to divide the number range into smaller segments and compute prime numbers in those segments one by one. This is an efficient way to reduce space complexity. This method is called a segmented sieve.

The optimization can be achieved in the following manner:

  1. Use a simple sieve to find prime numbers from 2 to Segmented Sieve and store them in an array.
  2. Divide the range [0…n-1] into multiple segments of size at most Segmented Sieve
  3. For every segment, iterate through the segment and mark the multiple of prime numbers found in step 1. This step requires O(Segmented Sieve) at max.

The regular sieve requires O(n) auxiliary memory space, whereas the segmented sieve requires O(Segmented Sieve), which is a big improvement for a large n. The method has a downside also because it does not improve time complexity.

Complexity Analysis

Space Complexity:

The simple sieve of eratosthenes algorithm requires O(n) memory space. And the segmented sieve requires
O(Complexity Analysis) auxiliary space.

Time Complexity:

The time complexity of a regular sieve of eratosthenes algorithm is O(n*log(log(n))). The reasoning behind this complexity is discussed below.

For a given number n, the time required to mark a composite number (i.e., nonprime numbers) is constant. So, the number of times the loop runs is equal to-

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

The harmonic progression of the sum of the primes can be deducted as log(log(n)).

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

So, the time complexity will be-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

Thus the time complexity O(n * log(log(n)))

Next, you’ll learn about Pascal’s Triangle

Summary

  • The Sieve of Eratosthenes filter out the prime numbers in a given upper limit.
  • Filtering a prime number starts from the smallest prime number, “2”. This is done iteratively.
  • The iteration is done up to the square root of n, where n is the given number range.
  • After these iterations, the numbers that remain are the prime numbers.
You Might Like: