## Saturday, July 20, 2013

### find the next prime after a list of known primes

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...