Torbjörn Granlund tg at
Wed Feb 12 17:53:23 UTC 2020

Some observations:

Around N, the average prime gap is log(N).  Right?

Therefore, we will probably need to pass log(N) composites on average
for typival usages of mpz_nextprime.

Adding a trial divisor prime p will eliminate 1/p of the composites.  We
can see it as being successful with 1/p probability for each composite.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list