# Sieve of Eratosthenes in Python

Manav Narula Feb 03, 2022

The Sieve of Eratosthenes is a very common algorithm to get the `prime numbers` below a given number. This number should be less than ten million.

The algorithm is simple to understand and is frequently implemented in programming. This tutorial will demonstrate implementing Python’s `Sieve of Eratosthenes` algorithm.

Let us begin by first understanding the logic behind this algorithm. First, we write all the numbers `between 2` and the provided number `Let us assume 50`.

Then we take the first prime number, `2`, and mark all the numbers greater than its square and `divisible by 2`. We then repeat the same with the next prime number, `3`.

The same procedure is carried out until the prime number 7 `square of the next number after 7 is 121 and greater than 50`. After marking all the numbers, the unmarked values are the prime numbers `till 50`.

The figure below demonstrates the final result. ## Use the Sieve of Eratosthenes in Python

We will first create a list of the required range. This list will mark `True` or `False` for the given index.

Initially, the list contains all elements as True. We will use a nested loop to make the changes and mark `non-prime` positions as `False`.

After this, we will store the positions where the value is still True in a new list. This list contains the prime numbers.

``````def sieve_of_eratosthenes(val):
max = val+1
lst = [True] * max
for i in range(2, int(val**0.5 + 1)):
if lst[i]:
for j in range(i*i, max, i):
lst[j] = False
final = []
for i in range(2, max):
if lst[i]:
final.append(i)
return final

print(sieve_of_eratosthenes(100))
``````

Output:

``````[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
``````

It is possible to make minor changes to the above code to improve the time complexity. For instance, we can use sets or dictionaries to filter non-prime numbers.

The final result is returned in a list, but use dictionaries or sets while marking the `prime` and `non-prime` numbers as `True` or `False`.

``````def sieveoferatosthenes_dict(n):
max = n+1
d = dict()
for i in range(2, max): d[i] = True

for i in d:
factors = range(i,max, i)
for f in factors[1:]:
d[f] = False
lst = [i for i in d if d[i]==True]
return lst
print(sieveoferatosthenes_dict(100))
``````

Output:

``````[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
``````

In the above example, we use the dictionary `d` for marking the values as `True` or `False` to filter out the prime numbers. The final result is in a list.

Author: Manav Narula

Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.