Re: smallest prime number greater than n

On Sep 24, 3:56 am, "KBH" <K...@xxxxxxxxxxx> wrote:
It's not necessary to generate all primes up to n but just determine if
the first odd number greater than n is prime, if the second odd number
greater than n is prime, and so on...

http://www.kbhscape.com/prime.htm

Oh, to determine if a single number is prime or not just divide the target
number by all odd numbers up to it's square root.


False. Testing for primality via trial division is one of the worst
ways to do it.

Consider the set {n, n+1, n+2, ....n + log^2 n}

sieve out those elements divisible by 2,3,5,7,....log^2 n.

Starting with the lowest untouched element, test each remaining one
for being a strong prp or a Frobenius prp. If you find a prp, prove
it
prime via ECPP or APR-CL.

.

Relevant Pages
Quantcast