Sieve of Eratosthenes to find Prime Numbers

Summary:This is a simple tutorial for Sieve of Eratosthenes in visual representation. Sieve of Eratosthenes is used to find prime numbers for given limit.

Sieve of Eratosthenes is an ancient and very efficient algorithm to find prime numbers within a given limit of less than 10 million.

Prime numbers are those numbers which are divisible by only 1 and itself. Note that 1 is neither prime nor composite number.

The process is very simple. The algorithm iteratively marks and excludes all the composite (non-prime) numbers which are basically multiples of prime numbers (starting from 2).

If you don’t understand this definition then scroll down for the visual example of the process.

Here is the pseudocode for the Sieve of Eratosthenes.

Let prime[] be array of boolean values of index 0-n (length=n+1)
Initially all values is True

loop from i=2 to √n (inclusive):
    if(prime[i]==True):
        loop from j=i^2, i^2+i, i^2+2i, i^2+3i.... upto n(inclusive):
            prime[j] = False
return all i for which prime[i]==True

Here is the python implementation of the pseudocode.

# n should be between 2 - 10 million
def sieveOfEratosthenes(n):
    # Array of True boolean value of index 0-n (length of array = n+1)
    prime = [True for i in range(n+1)]
    # Loop through the prime array from 2 to √n
    for i in range(2, int(len(prime)**0.5)):
        if(prime[i] == True):
            # Make all the multiples of i as composite starting from square of i
            for j in range(i*i, n+1, i):
                prime[j] = False
    # Print the output
    print(*[i if(prime[i]) else '' for i in range(2, len(prime))], sep=" ")


sieveOfEratosthenes(50)

The code may look tricky at first but it is simple.

1.) In the first step, we create an array of True boolean values from index 0 to n (array length will be n+1 as 0 is included).

The logic of array is that prime values will be kept as True while composite (non-prime) values will be turned to false after he end of the algorithm.

2.) Now we will iterate through the array from index 2 to the square root of n (√50 ~=7).

We are starting from index 2 because 0 and 1 are neither prime not composite numbers.

3.) The first iteration, which is at the array index 2. Mark all the numbers as composite numbers which are multiples of 2 and greater than or equal to the square of 2 (means >=4).

To mark as composite numbers we simply make the array value at that index as False.

4.) The second iteration the value of i will be 3. Mark all the numbers as composite numbers which are multiples of 3 and greater than or equal to the square of 3 (means >= 9).

In this iteration, the composite numbers divisible by 3 are excluded or marked as false.

---

5.) In the next iteration the value of i will be 4 but the condition prime[4] == True will fail so the loop will continue to next iteration.

---

6.) The value of i in the next iteration will be 5. Mark all the numbers as composite numbers which are multiples of 5 and greater than or equal to the square of 5 (means >= 25).

This iteration is completed and composite numbers divisible by 5 are marked.

7.) Next iteration will be at 6 but it is also marked as false which means composite.

8.) Now in this last iteration the value of i will be 7 and all its multiples greater than or equal to its square will be marked as composite.

In the end, all the array index from 2-n whose value will be true are prime numbers.

The time complexity of Sieve of Eratosthenes

The time complexity for the sieve of Eratosthenes is O(n log log n).