Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
The earliest known reference to the sieve (Ancient Greek: κόσκινον Ἐρατοσθένους, kóskinon Eratosthénous) is in Nicomachus of Gerasa's Introduction to Arithmetic,[3] an early 2nd century CE book which attributes it to Eratosthenes of Cyrene, a 3rd century BCE Greek mathematician, though describing the sieving by odd numbers instead of by primes.
As Sorenson notes, the problem with the sieve of Eratosthenes is not the number of operations it performs but rather its memory requirements.
[9] For large n, the range of primes may not fit in memory; worse, even for moderate n, its cache use is highly suboptimal.
The generation must be initiated only when the prime's square is reached, to avoid adverse effects on efficiency.
It can be expressed symbolically under the dataflow paradigm as using list comprehension notation with \ denoting set subtraction of arithmetic progressions of numbers.
Trial division has worse theoretical complexity than that of the sieve of Eratosthenes in generating ranges of primes.
A special (rarely, if ever, implemented) segmented version of the sieve of Eratosthenes, with basic optimizations, uses O(n) operations and O(√nlog log n/log n) bits of memory.
[16][17][18] Using big O notation ignores constant factors and offsets that may be very significant for practical ranges: The sieve of Eratosthenes variation known as the Pritchard wheel sieve[16][17][18] has an O(n) performance, but its basic implementation requires either a "one large array" algorithm which limits its usable range to the amount of available memory else it needs to be page segmented to reduce memory use.
Euler's proof of the zeta product formula contains a version of the sieve of Eratosthenes in which each composite number is eliminated exactly once.
