Best of all is libgmp .
It has a function that will scan the next simple number (using Miller-Rabin ), starting at some starting number.
void mpz_nextprime ( mpz_t rop, mpz_t op );
Set rop to the next prime greater than op.
This function uses a probabilistic algorithm to determine primes. For practical purposes, this is enough, the probability of a difficult passage will be extremely small.
You need this feature.
, , mpz_nextprime. - O(log(op)) ().
.