# Sieve of Eratosthenes Algorithm: Python, C++ Example

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.

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 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<=).

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 <=. Thus, traversing to 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.

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.

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 would be the prime numbers from 2 to 25.

## 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
for (int j = 2; j * j <= n; j++) {
// Update all multiples of i as false
for (int k = j * j; k <= n; k += j)
}
}
for (int i = 2; i <= n; 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):
# Update all multiples of i as false
for j in range(i * i, n+1, i):
i += 1
for i in range(2, n):
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 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 multiple of prime numbers found in step 1. This step requires O() at max.

The regular sieve requires O(n) auxiliary memory space, whereas the segmented sieve requires O(), 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() 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.