Python Sieve of Eratosthenes

What is the Sieve of Eratosthenes?

The Python Sieve of Eratosthenes is an algorithm that determines prime numbers within a specified range.

In this process, the multiples of all primes are marked as composite (i.e., not prime), starting with the first prime number. From a given prime, multiples of that prime are generated by generating sequences of numbers with a constant difference between them equal to the prime's value, and thus the multiples of that prime are derived. In contrast to using trial division to sequentially test the divisibility of each candidate number by each prime, the sieve tests every candidate number for divisibility simultaneously. When all multiples of a discovered prime have been marked as composites, the remaining unmarked numbers will be primes.

Code Implementation

Implementation of the Python sieve of Eratosthenes is shown below.

• You should begin with number 2 and increment it every step of the way until you arrive at an unmarked prime number x.
• All multiples of number x must be marked as not prime since number x is one of their divisors.
• An easy way to optimize: Make multiples of the number $x^x$ instead of 2x. Because all numbers between 2x and $x^x$ are already marked.

Let us look at an example to find prime numbers up to 15

Output:

Code Explanation:

During the first iteration, 2 is iterated till the square root of the number at the end is reached. When 'i' appears in the list, all its multiples are deleted. The for loop is used to accomplish this. 

range(i*2, number+1, i) – It will start from 2i and it takes a step of 'i' (2i, 3*i, etc.). If this number is found in the list, we will remove it using primes.remove(j).

Output Explanation

• Creating a list of all numbers from 2 to 15 is the first step.
• In this algorithm, any number greater or equal to the square of 2 is marked as divisible by 2.
• The numbers which will be removed in the above step are 4,6,8,10,12 and 14
• Next, we mark every number that is both multiples of 3 and greater than or equal to its square.
• The numbers which will be removed in the above step are 4,6,8,9,10,12,14 and 15
• The next number we are going to mark is 5 and we will mark all multiples of 5 that are greater than or equal to its square.
• The numbers which will be removed in the above step are 4,5,6,8,9,10,12,14 and 15
• We continue this process and our final list will look like [2, 3, 5, 7, 11, 13]
• These unmarked numbers are our prime numbers between 1 to 15.

Time Complexity

In this algorithm, the composite numbers are marked and then removed from the list by assigning them. Marking a composite number and assigning a value takes time. In this algorithm, the complexity lies in the number of loops that are run to mark the composite numbers.

By assigning the value 0 to the multiples of the current prime number in L, we remove the composite numbers. Consider the prime number 2 as our current prime number. As part of the first iteration, elements will be marked with N/2. In the same way, when our current prime number is 3, we assign N/3 composite numbers. We would run the loop a total of:

N/2 + N/3 + N/5 + ...

Here is the equation we need to solve

N * (1/2 + 1/3 + 1/5 + ...)

It is possible to prove the following using the Harmonic Progression of the sum of primes:

( 1/2 + 1/3 + 1/5 + .....) = log(log(N))

Thus, the Sieve of Eratosthenes algorithm has a total time complexity of O(Nlog(log(N)))

Space Complexity

A problem's space complexity can be easily explained as the amount of memory it consumes when it is executed.

The space complexity is calculated not only based on the variables in the problem/algorithm but also by the variables.

Space Complexity = Auxiliary Space + Space used for input values

The term "auxiliary space" refers to the temporary space that is required by an algorithm to function. You can think of temporary arrays, pointers, etc.

When comparing standard sorting algorithms based on space, Auxiliary Space is better than Space Complexity when comparing standard sorting algorithms.

The concept of space complexity is similar to the concept of time complexity. The space required to create an array of size n will be O(N). The space required to create an n-dimensional array will be O(N2).

The space complexity of the Sieve of Eratosthenes algorithm is O(N)

More Examples for Understanding

Let us look at some more examples to understand the Sieve of Eratosthenes algorithm in Python

Example 1:

Output:

Code explanation:

• Step 1: The user first enters the upper limit of the range and stores it in a variable n.
• Step 2: The sieve_value is initialized to a set of numbers from 2 to n (n+1 is not included).
• Step 3: The while loop ensures that the sieve_value isn't empty.
• Step 4: A variable prime is initialized with the least number in the sieve and its prime number is printed.
• Step 5: All multiples of the prime number are then removed from the sieve.
• Steps 4 and 5 continue until the sieve_value is empty.

Example 2:

Output:

Code explanation:

• Get the value N from the user.
• Assign all values to TRUE in a boolean array of size N+1, prime[N+1].
• There is no prime between 0 and 1; therefore, prime[0] = prime[1] = FALSE.
• A loop is formed by looping from 2 to root(N) with a variable i.
• If prime[i] is TRUE, then all multiples of i in the array will be false.
• For each value 'p' in the array, print TRUE if prime[p] is true

Example 3:

Output:

Code Explanation:

Our first step is to create a boolean list where all values are initialized with True. It is False if a value is not prime, otherwise, it is True. In the next iteration, we iterate from 2 till the square root of the number, updating the multiples to False as well. The loop is repeated from 2*i to n+1 with a step of j+1.

Once we have our final list, we can check the values. Whenever a value is True in any index, we print the number as prime.

Similar Python Programs

Have a look at these two articles to get an even more better understanding of sieve of eratosthenes algorithm

Extended Seive

Segmented Seive