Understanding the Sieve of Eratosthenes Algorithm to Find Prime Numbers with Python Code

Posted on by

Introduction

Finding prime numbers is a common task in mathematics and computer science. Prime numbers have fascinated mathematicians for centuries, and they play a crucial role in many fields, including cryptography and number theory. In this blog post, we will explore the Sieve of Eratosthenes algorithm and its implementation using a Python code. It is simple and one of the efficient algorithm for finding prime numbers up to a given number.

What is the Sieve of Eratosthenes Algorithm?

The Sieve of Eratosthenes is an ancient algorithm developed by the Greek mathematician Eratosthenes around 200 BCE. It is a systematic method for finding all prime numbers up to a given limit. The algorithm works by iteratively marking the multiples of each prime number, starting from 2, as composite (i.e., not prime). The unmarked numbers that remain are prime.

How Does the Algorithm Work?

Let’s break down the steps of the Sieve of Eratosthenes algorithm:

  1. Create a list of consecutive integers from 2 to a given limit.
  2. Start with the first prime number, 2.
  3. Mark all multiples of 2 as composite.
  4. Find the next unmarked number (which is a prime) and repeat steps 3 and 4 until you reach the square root of the given limit.
  5. All unmarked numbers remaining in the list are prime.

Implementing the Sieve of Eratosthenes Algorithm in Python

Now, let’s see how we can implement the Sieve of Eratosthenes algorithm using Python code:

def SieveOfEratosthenes(num):
    # Create a boolean array 'prime' with True values for indices 0 to num
    prime = [True for i in range(num + 1)]
    p = 2

    # Mark multiples of each prime number as False
    while p * p <= num:
        if prime[p]:
            for i in range(p * p, num + 1, p):
                prime[i] = False
        p += 1

    # Print the prime numbers
    for p in range(2, num + 1):
        if prime[p]:
            print(p)

if __name__ == '__main__':
    num = 40
    print("Following are the prime numbers smaller than or equal to", num)
    SieveOfEratosthenes(num)

Let’s break down the code:

– We start by creating a list called `primes` with `limit + 1` elements, all initialized as `True`. We set the first two elements (`primes[0]` and `primes[1]`) to `False` because 0 and 1 are not prime numbers.
– We iterate over the numbers from 2 to the square root of the given limit. For each prime number, we mark its multiples as `False` in the `primes` list.
– Finally, we create a new list called `prime_numbers` and populate it with the indices of the `primes` list that are still `True`.

Understanding the code

  • We create a boolean list called prime with True values for indices 0 to num.
  • We initialize p to 2 (the first prime number).
  • While p * p is less than or equal to num:
    • If prime[p] is True, we mark all multiples of p as False.
    • increment p.
  • Finally, we print the prime numbers (where prime[p] is still True).
#Output of above code
Following are the prime numbers smaller than or equal to 40
2
3
5
7
11
13
17
19
23
29
31
37

Conclusion

The Sieve of Eratosthenes algorithm is a powerful and efficient method for finding all the smaller prime numbers. By iteratively marking the multiples of each prime number, we can quickly identify all the prime numbers up to a given limit. Python provides a simple and elegant way to implement this algorithm, making it accessible to programmers of all levels.

Remember, the beauty of mathematics lies not only in its elegance but also in its practical applications. Happy coding!