Sieve of Eratosthenes

The Sieve of Eratosthenes is often one of the first algorithms taught in
computer science books. This simple algorithm showcases the ability
to calculate primes numbers through the power of a computer without learning
much of the nuts and bolts of a programming language. Finding the
first 100 prime numbers can be done in a fraction of a second, and the
first 1000 prime numbers performed in a split second. It definitely proves to have a
computer around to aid in computation!

From Wikipedia, here is an animation of how the algorithm works:

Animation showing the Sieve of Eratosthenes

The above animation uses the Sieve of Eratosthenes to find all prime
numbers up to 120.

The number 2 is chosen first as the starting point and first prime. Then, all multiple values of 2
are crossed off (in red) from being prime numbers. Next, number 3 is chosen as a
prime number, and all multiple values of 3 (in green) are crossed off from being
possible prime numbers. Since the number 4 is already marked off as red from being
a multiple of 2, the number 5 is chosen as the next starting point and saved as a prime. This continues
until all positions are either chosen as prime or crossed off.

If n is the value that we want to check prime numbers until, then we will ever cross off
multiples up to sqrt(n), because all multiples of sqrt(n) above sqrt(n) are larger than n.
(This is because we would only ever multiple sqrt(n) by values larger than sort(n) by the
time we get there, since values smaller than sqrt(n) have been crossed off).

The mod operation comes to mind when checking for prime numbers.
Here is the Sieve of Eratosthenes using the mod operation:

And here it is without using mod!

Leave a Reply