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

Okay, seriously, what are your needs? You could generate a (pseudo) random number in that range and pick the next larger or smaller prime, depending on which end you are nearer. — Daniel Fischer, Dec 02 '12 at 01:17
You have to decide what you mean by random. What is the distribution? — Don Reba, Dec 02 '12 at 01:24
Welcome to C! The only "built in" functions are very general. There is nothing built in that is anywhere near as specific as this. — Nocturno, Dec 02 '12 at 03:12

score 11 · Accepted Answer · answered Dec 02 '12 at 01:19

11

You can do this efficiently like so:

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

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

answered Dec 02 '12 at 01:19

IVlad

43,099
13
111
179

I suspect that by random he means uniformly distributed within the set of prime numbers. Your solution won't be, because random numbers are not uniformly distributed. It might be close enough, though. – Don Reba Dec 02 '12 at 01:21
2

@Don Reba: As long as the input random numbers are uniformly distributed in the range, the primes chosen by this method will be uniformly distributed among the primes in that range, too. – caf Dec 02 '12 at 01:39
There's no need to use a probabilistic test like Miller-Rabin - 1 billion is small enough for trial factorisation to be feasible. – caf Dec 02 '12 at 02:00
1

Don't forget that it is possible that if you pick the wrong range, there are no prime numbers at all in the selected range. Make sure that your code will exit gracefully if it doesn't find anything after enough (for some value of 'enough') tries. Infinite loops can really slow down your program. – rossum Dec 03 '12 at 19:32

score 3 · Answer 2 · answered Dec 02 '12 at 01:12

3

When I had to do this I created a function called isPrime(). isPrime() would check and determine if a number was prime.

isPrime() had two different functions one that would run forever and print every prime number and another that would run up to a certain number.

You could populate an array with all of the prime numbers between i and j. Then generate a random number that is less than or equal to the size of the array. Use this random number to select an element from the array.

Hope this helps!

answered Dec 02 '12 at 01:12

Chris.Stover

516
6
14

Those easy-to-use `uint64_t[1000000000ull]` arrays – Lightness Races in Orbit Dec 02 '12 at 01:14
@chris This will be very slow .. I need a faster solution . – premprakash Dec 02 '12 at 01:18
2

What you need is to put some thought into the problem! You're expecting magic. – Lightness Races in Orbit Dec 02 '12 at 01:18
Prem, I agree that it will be very slow. I wasn't trying to provide the worlds most efficient solution. One workaround for this would be to pre-load the data in the array and store it locally. – Chris.Stover Dec 02 '12 at 04:17

score 3 · Answer 3 · answered Dec 02 '12 at 04:23

To generate a random number between two bounds do this

extern unsigned int urand();
int lower = 1000000;
int upper = 1000000000;
int p = urand() % (upper - lower) + lower;

To test if a number near 1 billion is prime it is sufficient to do trial division by all primes < sqrt(1 billion) = 31622. There are about 3400 such primes. Make an array

unsigned short primes[3400] = { 2, 3, 5, .. 31657 }

and divide by them all. If all trial divisions have remainder != 0 then the number is prime.

I doubt any of the more sophisticated primality tests will be faster for such small primes.

I compared trial division with primes to an optimized primality test in this range. Trial division took 53 times longer (22 microseconds vs. 0.4 microseconds). It may be good enough, but in this range there's serious benefit to a faster test, since otherwise you need thousands of divisions. — Charles, Jun 21 '13 at 13:37

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

3 Answers3

Linked