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.
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.
iwill 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).
5.) In the next iteration the value of
i will be 4 but the condition
prime == 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).
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).