What I've been thinking about...

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.

- themiddlepane likes this
- summer-well likes this
- anengineersaspect reblogged this from backwardinduction
- mylifeisborromean reblogged this from backwardinduction
- backwardinduction reblogged this from memeengine
- godual likes this
- smoot reblogged this from princecortex
- imcatdragon reblogged this from contemplatingmadness
- classicalcoop reblogged this from logicianmagician
- elcosmonumero likes this
- isometries reblogged this from logicianmagician
- gallopinggroundsloth likes this
- logicianmagician reblogged this from princecortex
- imcatdragon likes this
- shinblr likes this
- logicianmagician likes this
- princecortex reblogged this from memeengine
- 14-billion-years-later likes this
- environmentalemily likes this
- environmentalemily reblogged this from contemplatingmadness
- virginpancakes reblogged this from contemplatingmadness
- cellular-automaton likes this
- cavalierzee reblogged this from contemplatingmadness
- cavalierzee likes this
- sunshinerepublic reblogged this from purple-madness
- purple-madness reblogged this from contemplatingmadness
- intothecontinuum likes this
- bloodredorion likes this
- contemplatingmadness reblogged this from memeengine
- pjacayton reblogged this from memeengine
- pjacayton likes this
- memeengine posted this