Sieve of Eratosthenes22 Aug 2015
I’m using this post to introduce the Sieve of Eratosthenes, which is currently my favorite algorithm. See the Java implementation below:
The Sieve of Eratosthenes is a 1900 year old algorithm that can efficiently find all of the prime numbers under a given number. The work of finding prime numbers is no trivial task in the world of computing: RSA cryptosystems, for instance, rely on the factorization of one large number into two prime numbers. Prime numbers also play a role in the generation of psuedo-random numbers. Such examples underscore the importance of quickly generating primes in computing, and the Sieve of Eratosthenes does just that. To describe the algorithm’s process, I will refer to the inputted upper boundary as :
- Every number between 2 and is listed.
- Iterate through each number
- If the number is less than or equal to and is prime, label all of its multiples under as composite (not prime).
- After all numbers have been iterated through, the ones not labeled as composite are prime.
The GIF below is incredibly helpful for those with a more visual predilection. When watching it, consider the quote
Sift the Two’s and Sift the Three’s, The Sieve of Eratosthenes. When the multiples sublime, The numbers that remain are Prime.
Most research states that this particular implementation of the sieve is the most efficient algorithm for determining primes under .
Given the fact that this algorithm is , the code completes amazingly quick for inputs under the specified range. As the input gets larger, however, it becomes necessary to switch to other sieves due to memory constraints. Even so, other sieves use a similar approach to this one.
I’ve used the above code to optimize my solutions to Project Euler problems, one of which asked to find the sum of all the primes below two million. The solution was calculated in less than five seconds.
That, in essence, is what makes this algorithm so great. In less time than it takes to drink a couple ounces of coffee, a wild number of prime numbers can be calculated.