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:

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!