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. -- Torbjörn Please encrypt, key id 0xC8601622