Ok suppose you have a list of known primes like:

{2,3,5,7}

You'd like to know if the next odd number is prime:

So assume you're list of primes is:

{2,3,5,7,9}

Of the 9 numbers from 1 to 9 we know that roughly 9/2 -1 will be composite with a factor of 2.

So 9-3 = 6

Of these 6, 6/3 - 1 will divide 3 but not 2.

6-1=5 possible remaining primes

of these 5 5/5 -1 will divide 5 but not any previous prime

5-0=5

And then the same kind of thing for 9 so:

5-0 = 5.... saying that there are 5 primes up to 9, but one more thing is if you think of the 5 numbers this process leaves in the list, the number 1 hasn't been accounted for. So 5-1 = 4, saying there are only 4 primes in our list contradicting the fact that there are 5. Therefore 9 is not prime.

Now suppose we skip 9 as a possible prime and move on to 11...

{2,3,5,7,11}

11/2 -1 = 4

11-4 = 7

7/3-1 = 1

7-1 = 6

6/5 - 1 is 0

6-0 is still 6 and

6/7 -1 is 0

and 6/11 is 0,

so then we do the final step as we did above of removing the number 1 from the list of possibilities, giving that there are 5 primes in the list, confirming our assumption.

So I don't know if this always works, I'll write a program to try and generate the list of the first 1000 primes or something in this way so expect an update...

## No comments:

## Post a Comment