smoot

memeengine:

Sieve of Eratosthenes (aka the Prime Sieve)

The Prime Sieve is nothing less, and nothing more, than an efficient way to find Prime Numbers within a certain range.

Checking if a number is Prime (which means it has no divisors besides 1 and itself) is time-expensive.  To check if (for instance) the number 11 is prime, one must divide 11 by 2 and check the result, then divide by 3, then divide by 4… all the way up to dividing by 10.  This means 10 operations, and in terms of computing, it’s a little convoluted in terms of if/then’s.

And this is just for the number 11, where division is quick.

The way to speed it up, is to look for non-primes (aka composite numbers) and rule them out.  Say you want to find the primes between 1 and 100.  You know (for example) that all the multiples of 5 are not prime (since they can be divided by 5).  So, you cross off 10, 15, 20, … right up to 95, 100.  So, in the case of 95, you just proved it composite in one (easy) operation, instead of checking all the 94 numbers below it for divisibility.

The systematic way to do this is to start at the bottom.  Cross off all the multiples of 2.  Now move up the list to the next number not yet crossed out… you arrive at 3.  You then cross out all the proper multiples of 3, and move on to the next uncrossed number…

Each time you move to the next uncrossed number, you are guaranteed it is prime.  Why?  Take the number 17.  When you come to 17 uncrossed, you have already checked the multiples of all the lower numbers, and found that 17 was not a multiple of any.  Thus it has no divisors, and is prime.

So for the prime numbers, it seems NO operations are required to decide!

The animation below is from the Wikipedia page on the subject, and demonstrates ruling out the composites up to 120.