Sieve of Eratosthenes in Python
What is Sieve of Eratosthenes?
The Sieve of Eratosthenes is a simple and efficient algorithm used to find all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime number, starting from 2, up to the limit.
The algorithm proceeds as follows:
- Create a list of all integers from 2 to the given limit.
- Set a variable p to 2, the smallest prime number.
- Mark all the multiples of p as composite (i.e., not prime).
- Find the next smallest prime number, which is the next unmarked number greater than p. If there is no such number, the algorithm is complete.
- Set p to the next prime number found in step 4 and repeat from step 3.
At the end of the algorithm, all the unmarked numbers in the list are prime. The algorithm is named after the ancient Greek mathematician Eratosthenes, who used a similar method to find primes more than 2,000 years ago.
The Sieve of Eratosthenes is very efficient for finding prime numbers up to a few million, but it becomes less practical for larger limits due to the amount of memory required to store the list of integers.
Example:
Here is an implementation of the Sieve of Eratosthenes in Python:
# Python program to print all Primes Smaller
# than or equal to N using Sieve of Eratosthenes
def SieveOfEratosthenes(num):
prime = [True for i in range(num+1)]
# boolean array
p = 2
while (p * p <= num):
# If prime[p] is not
# changed, then it is a prime
if (prime[p] == True):
# Updating all multiples of p
for i in range(p * p, num+1, p):
prime[i] = False
p += 1
# Print all prime numbers
for p in range(2, num+1):
if prime[p]:
print(p)
# Driver code
if __name__ == '__main__':
num = 20
print("Following are the prime numbers smaller"),
print("than or equal to", num)
SieveOfEratosthenes(num)
Output:
Following are the prime numbers smaller
than or equal to 20
2
3
5
7
11
13
17
19
Explanation:
In this program, we first define the SieveOfEratosthenes(num)function, which takes an integer num as input and returns a list of all prime numbers up to num. The function implements the Sieve of Eratosthenes algorithm as described earlier.
Next, we take user input for the upper limit of the range of prime numbers, using the input() function and converting the input to an integer using the int() function.
We then call the SieveOfEratosthenes() function with the input num to find all prime numbers up to num. Finally, we display the list of prime numbers using the print() function.
Characteristics of Sieve of Eratosthenes
The Sieve of Eratosthenes is a very efficient algorithm for finding all prime numbers up to a given limit. Here are some of its characteristics:
- Time Complexity: The time complexity of the algorithm is O(n log log n), which means that it is very efficient for finding all primes up to a few million. This makes it much faster than other methods such as trial division.
- Space Complexity: The algorithm requires O(n) space to store the list of integers, which can be a limitation for very large values of n.
- Easy to Implement: The algorithm is very simple and easy to understand, making it a popular choice for finding primes in programming competitions and coding interviews.
- Deterministic: The algorithm is deterministic, meaning that it always produces the same output for a given input.
- Not suitable for large values of n: While the algorithm is efficient for finding primes up to a few million, it becomes less practical for larger values of n due to the amount of memory required to store the list of integers.
- Useful for generating primes: The algorithm is useful for generating a list of prime numbers up to a given limit, which can be used for other purposes such as encryption, hashing, or generating random numbers.
Advantages of sieve of Eratosthenes
The Sieve of Eratosthenes algorithm has several advantages. Some of them are as follows:
- It is a simple and efficient algorithm for finding prime numbers up to a given limit.
- The algorithm has a time complexity of O(n log log n), which is significantly faster than other algorithms for finding prime numbers, such as trial division.
- The algorithm is easy to implement and understand, and can be used to find prime numbers in small to medium-sized ranges.
- The algorithm uses very little memory, as it only requires a Boolean list of size n+1 to store whether each number is prime or not.
- The algorithm can be easily modified to find all prime factors of a given number, by marking all multiples of each prime number as not prime.
Overall, the Sieve of Eratosthenes algorithm is a powerful and efficient method for finding prime numbers up to a given limit, and has many practical applications in computer science and mathematics.