Sieve of Eratosthenes : Best Approach to Find Prime Numbers upto ‘n’
Hi Everyone! In this Article I’ll discuss about one of the most important algorithms related to number theory which is Sieve of Eratosthenes. This algorithm is considered as one of the best approaches to find all prime numbers upto a specific range i.e. from 2 to n.
Let’s have a discussion about it that why it’s important. Generally people doesn’t bother about such simple algorithms like prime number generation but these algorithms are very essential and vital in terms of decreasing the time complexity of a program upto the great extent.
The traditional approach to this problem is to create two functions called isPrime(n) and generatePrime(n).
Traditional Approach to Find Prime Numbers
def isPrime(n): for i in range(2,n**2+1): if n%i==0: return False return True def generatePrime(m): l= for i in range(2,m+1): if isPrime(i): l.append(i) return(l)
This approach is very useful in generating the prime numbers but it’s lengthy and takes O(n√n) which may be critical when the constraints for the input become a large number.
The better approach with lesser time complexity to this problem is to create a sieve and then store the status of each element whether they are prime or not. The Sieve of Eratosthenes is an ancient mathematical algorithm that can find all prime numbers up to n. The algorithm deals with the fact that if a number is prime, any multiple of that algorithm is not prime i.e. they are composite. The below Image Can Explain this Algorithm in an easy way:
Let’s have a look over this algorithm:
generatePrime(n): int prime[n+1]; for i = 0 to n: prime[i] = 1 prime = 0 prime = 0 for i = 2 to n: if prime[i] == 1: for (j=2;i*j<=n;j++): prime[i*j]=0
Therefore within the array, the element indices having value 1 are prime numbers which can be later used by a programmer according to their comfort.
The Explanation for the above algorithm is given in the video added below:
Now, Let’s Try to implement this algorithm in Python:
def generatePrime(n): prime = [1 for i in range(n+1)] prime = prime = 0 for i in range(2,n+1): if prime[i]==1: for j in range(2,n//i+1): prime[i*j]=0 l=[i for i in range(2,n+1) if prime[i]==1] return l
The output for the above code is as follows:
The Program is the implementation of the Algorithm Stated Above. For Explanation kindly refer to video mentioned below: