Sieve of Eratosthenes in Python & C++

What Is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is the simplest prime number sieve. It is a prime number algorithm used to discover every prime number within a given limit. Several prime sieves exist, including the Sieve of Eratosthenes, the Sieve of Atkin, and the Sieve of Sundaram.

The word “sieve” refers to a utensil that filters substances. In the same spirit, the sieve algorithm in Python and other languages refers to a method that filters out prime numbers from a list of integers.

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

Why Use the Sieve of Eratosthenes?

In the Sieve of Eratosthenes method, a small prime number is selected first, and all multiples of it are filtered out. The process runs in a loop across a given range, producing every prime up to n efficiently without performing trial division on each candidate.

This makes the sieve faster than checking primality one number at a time. It is widely used in number theory, cryptography, hashing, and competitive programming where many primes must be generated quickly.

For example:

Let us take the number range from 2 to 10.

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

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 because 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 number.

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 is less than or equal to the square root of n (x<=).

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

n = a * b

Again, n = *

= (factor smaller than ) * (factor larger than )

So at least one of the prime factors or both must be <= . Therefore, traversing up to will be enough.

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

Worked Example

Example:

Let us 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 since we selected n = 25.

Step 2) Then we select the smallest number on the list, x. Initially x = 2 because 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 are: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

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.

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

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

Pseudo-Code

The following pseudo-code captures the basic structure of the Sieve of Eratosthenes before we translate it into actual 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

Below is a complete C++ implementation of the Sieve of Eratosthenes that prints every prime up to a chosen upper bound.

#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

The following Python program implements the same algorithm using a boolean list and a while loop.

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 runs a loop through the whole number range. Therefore, it needs O(n) memory space to store the numbers. The situation becomes complicated when we try to find primes in a huge range, because it is not feasible to allocate such a large memory block 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 and store them in an array.
2. Divide the range [0…n-1] into multiple segments of size at most .
3. For every segment, iterate through the segment and mark the multiples of the prime numbers found in step 1. This step requires O() at maximum.

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

Complexity Analysis

Understanding both space and time complexity helps you choose between the regular sieve and the segmented sieve for a given problem size.

Space Complexity:

The simple Sieve of Eratosthenes algorithm requires O(n) memory space. The segmented sieve requires O() 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 (that is, a non-prime number) 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 deduced 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 is O(n * log(log(n))).

Next, you will learn about Pascal’s Triangle.

FAQs