Sieve of Eratosthenes in Python

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.

Prime Numbers 1 to 50 using sieve of eratosthenes

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 Narula avatar Manav Narula avatar

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

Related Article - Python Algorithm

  • Smith-Waterman Algorithm in Python
  • Rabin-Karp Algorithm in Python
  • Union-Find Algorithm in Python
  • Depth-First Search in Python
  • Linear Search in Python