Sieve of Eratosthenes
The Sieve of Eratosthenes is a simple and efficient algorithm used to find all prime numbers up to a given limit. This algorithm was discovered by the ancient Greek mathematician Eratosthenes, who lived around 250 BC. The algorithm is named after him, and it is one of the oldest known algorithms.
The basic idea behind the algorithm is to start with a list of all numbers up to the given limit, and then to remove all the composite numbers from the list by iteratively marking their multiples as composite. The remaining numbers that are not marked as composite are the prime numbers.
Algorithm
- Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
- Initially, let p equal 2, the smallest prime number.
- Mark all the multiples of p greater than or equal to 2p but less than or equal to n. Specifically, mark the multiples 2p, 3p, 4p, ..., np.
- Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
- When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.
Example
Let's use the Sieve of Eratosthenes to find all the prime numbers up to 30.
- Create a list of consecutive integers from 2 through 30: (2, 3, 4, ..., 30).
- Mark all the multiples of 2 greater than or equal to 2*2 = 4 but less than or equal to 30. Specifically, mark the multiples 4, 6, 8, ..., 30.
- Find the smallest number in the list greater than 2 that is not marked. This is 3.
- Mark all the multiples of 3 greater than or equal to 2*3 = 6 but less than or equal to 30. Specifically, mark the multiples 6, 9, 12, ..., 30.
- Find the smallest number in the list greater than 3 that is not marked. This is 5.
- Mark all the multiples of 5 greater than or equal to 2*5 = 10 but less than or equal to 30. Specifically, mark the multiples 10, 15, 20, ..., 30.
- Find the smallest number in the list greater than 5 that is not marked. This is 7.
- Mark all the multiples of 7 greater than or equal to 2*7 = 14 but less than or equal to 30. Specifically, mark the multiples 14, 21, 28.
- There are no more numbers in the list that are greater than 7 and not marked. The remaining numbers that are not marked in the list are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, which are all the primes below 30.
Complexity
The time complexity of the Sieve of Eratosthenes algorithm is O(n log log n), where n is the limit up to which we want to find the prime numbers. This is because each composite number is marked only once, and the number of composite numbers up to n is O(n log log n). The space complexity of the algorithm is also O(n), as we need to store a list of n numbers.
Conclusion
The Sieve of Eratosthenes is a simple and elegant algorithm that is used to find all prime numbers up to a given limit. It is one of the oldest known algorithms and is still widely used today. The algorithm is easy to implement and has a time complexity of O(n log log n), which makes it very efficient for finding prime numbers for small to medium-sized values of n.