Sieve of Eratosthenes
Introduction
The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking the multiples of each prime number, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with a constant difference between them that is equal to that prime. This is the key distinction between using the Sieve of Eratosthenes and using trial division to sequentially test each candidate number for divisibility by each prime. Once all the multiples of each discovered prime are marked as non-prime, the remaining unmarked numbers in the list are primes.
History
The Sieve of Eratosthenes is named after the ancient Greek mathematician Eratosthenes, who was the chief librarian at the Library of Alexandria. He is credited with its invention in the 3rd century BC. The Sieve was one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so.
Algorithm
The algorithm of the Sieve of Eratosthenes is straightforward and simple to implement. It operates on a list of numbers from 2 to a specified upper limit n. The algorithm iteratively takes the next unmarked number in the list and marks all its multiples. This process continues until all numbers in the list have been either marked or confirmed as prime.
Pseudocode
The following pseudocode demonstrates the Sieve of Eratosthenes algorithm:
``` Algorithm Sieve of Eratosthenes(n)
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n:
if A[i] is true:
for j = i^2, i^2+i, i^2+2i, i^2+3i, ..., not exceeding n:
A[j] := false
return all i such that A[i] is true.
```
Complexity Analysis
The time complexity of the Sieve of Eratosthenes is O(n log log n), which makes it one of the most efficient algorithms for finding all primes up to a given number n. The space complexity is O(n), as the algorithm requires a Boolean array of size n to mark the multiples of primes.
Variations and Optimizations
There are several variations and optimizations of the Sieve of Eratosthenes that aim to improve its efficiency or reduce its memory usage. These include the Segmented Sieve, the Sieve of Sundaram, and the Sieve of Atkin.
Segmented Sieve
The Segmented Sieve is a variation of the Sieve of Eratosthenes that divides the range 2 through n into segments of size √n. This reduces the memory requirements to O(√n), making it possible to find primes up to larger values of n.
Sieve of Sundaram
The Sieve of Sundaram is a sieve that finds all primes less than a given value n. It does so by eliminating certain integers of the form i + j + 2ij where i, j are non-negative integers. The remaining numbers are doubled and incremented by one, giving all the odd prime numbers (and 2).
Sieve of Atkin
The Sieve of Atkin is a modern algorithm introduced by Atkins and Bernstein in 2004. It is an optimized sieve algorithm, and its run-time complexity improves upon the Sieve of Eratosthenes and the Sieve of Sundaram for generating all primes below a given number n.
Applications
The Sieve of Eratosthenes has many applications in both theoretical and applied mathematics. It is used in the field of number theory, particularly in the study of prime numbers. It is also used in cryptography, specifically in the generation of large prime numbers for public key algorithms.