# Sieve of Eratosthenes in Python

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.

**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.

LinkedIn