Generate Random Prime number in C/C++ between 2 limits

Question

Is there a built in function that can generate a random prime number between 2 given limits in C/C++?

I want a function that can generate a random prime number between 1 million and 1 billion

Answer 1

You can do this efficiently like so:

1. Generate a random number in that interval;
2. Check if it is divisible by any of the first few primes (say 2 .. 17, experiment for best results). If yes, go to 1;
3. Use Miller-Rabin to test for primality.

Also see this for a similar, a bit more complex, idea.