## The Sieve of Eratosthenes For Finding Primes

##### Eratosthenes of Cyrene

I first saw this algorithm to efficiently compute prime numbers while taking my first year computer science class.  According to The Prime Glossary it was known to have been introduced circa 240 B.C.  It was created by Eratosthenes of Cyrene (c. 276 – 194 B.C. ) who was born in Cyrene, a Greek colony west of Egypt.   It is known that Eratosthenes was a very versatile scholar and that he wrote on mathematics, geography, astronomy, history, philosophy and literary criticism.   Besides his works in mathematics he is most known for his chronology of ancient history and for his famous measurement of the size of the earth. Although none of his works have survived, the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nichomachus.

##### What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer.  In fact it is one of the most efficient ways to find the smaller primes (below 10 million or so).   It is quite a simple algorithm and is not very hard to understand.  It is defined neatly and concisely in words at The Prime Glossary page for the Sieve of Eratosthenes and is reproduced below:

Make a list of all the integers less than or equal to n (and greater than one). Strike out the multiples of all primes less than or equal to the square root of n, then the numbers that are left are the primes.

The Sieve of Eratosthenes wikipedia page has a nice animation of how the sieve works and I have included it below.

The algorithm makes use of the fact that a composite integer is divisible by a prime not exceeding it’s square root.  So, to find the number of primes not exceeding 100, first note that the composite integers not exceeding 100 must have a prime factor not exceeding 10.  Because the only the primes less than 10 are 2, 3, 5, and 7, the primes not exceeding 100 are these four primes and those positive integers greater than 1 and not exceeding 100 that are divisible by none of 2, 3, 5, or 7.

Consequently, the following procedure can be used to find primes not exceeding a number N,  100 this  instance. Accordingly, first the integers that are divisible by 2, other than 2 are deleted. Since 3 is the first integer greater than 2 that is left, all those integers divisible by 3, other than 3 are deleted.  Since 5 is the next integer left after 3, those integers divisible by 5, other than 5, are deleted. The next integer left is 7, so those integers divisible by 7, other than 7, are deleted.  Since all composite integers not exceeding 100 are divisible by 2, 3, 5, or 7, all remaining integers except 1 are prime.  Visually this process can be seen below at each stage.

The table displays those integers deleted at each stage, where each integer divisible by 2, other than 2, is underlined in the first panel, each integer divisible by 3, other than 3, is underlined in the second panel, each integer divisible by 5, other than 5, is underlined in the third panel, and each integer divisible by 7, other than 7, is underlined in the fourth panel.  Finally, the integers left not underlined in the fourth panel are the primes not exceeding 100.

##### Optimized Algorithm Starting from Squares

It’s also worth noting here at this point that there is a more optimized implementation of this algorithm starting from squares.

I have implemented it in Java below:

##### Algorithm Complexity

According to the Wikipedia page the time complexity of calculating all the primes below n is $O(n \log\log n)$ and is a direct consequence of the fact that the prime harmonic series asymptotically approaches $\log \log n$. It has an exponential time complexity with regard to input size, though, which makes it a pseudo-polynomial algorithm.  The bit complexity of the algorithm is $O(n (\log n) (\log \log n))$ bit operations with a memory requirement of $O(n)$.