Random Primes between 4000000000 and 4294967291 (C++) What is an efficient way to find a random prime between $4000000000$ and $4294967291 $ in C++?
This is what I wrote, but it is ridiculous:
unsigned long long rand_prime()
{
vector<unsigned long long> vect_prime;

int count = 0;

for( unsigned long long i = 4000000000 ; i <= 4294967291 ; ++i )
{
    for( unsigned long long j = 1 ; j <=i ; ++j )
    {
        if( i % j == 0 )
        {
            ++count;
        }
        cout << "CAT";
    }

    if( count == 2 )
    {
        vect_prime.push_back( i );
    }
    cout << "DOG";
    count = 0;
}

return vect_prime[ rand() % vect_prime.size() ];
}

It takes so long to get to DOG.
 A: Here's some simple code. It can be improved, but this version takes about 25,000 divisions compared to 1,223,372,019,527,422,987 in your version (making it several trillion times faster).
int isprime(unsigned long long n) {
  /*if((n&1)==0) return n==2;*/
  if(n%3==0) return n==3;
  /*if(n<25) return n>1;*/
  unsigned long long p = 5;
  while (p*p <= n) {
    if (n%p==0) return 0;
    p += 2;
    if (n%p==0) return 0;
    p += 4;
  }
  return 1;
}

unsigned long long rand_prime(int lower, int upper) {
  unsigned long long spread = upper - lower + 1;
  while(1) {
    unsigned long long p = 1 | (rand() % spread + lower);
    if (isprime(p)) return p;
  }
}

/* Usage:
unsigned long long r = rand_prime(4000000000, 4294967291);
*/

The basic idea: generate a random number in that range, then test it to see if it's prime. Instead of checking for divisibility by all numbers up to the number being tested, it checks only the odd numbers not divisible by 3 up to the square root of the number.
This could be improved with Miller-Rabin pretesting, or even a Lucas test to prove primality below 2^64.
A: It is possible to represent all the 32-bit primes as map of odd numbers representing each odd number with a bit. It takes about 256 megabytes for this map, but memory is cheap these days. (If you only represent the odd 32-bit numbers greater than 0x40000000, this map will be a lot smaller, but you should first compute all of the 32-bit primes.) Since 256 megabytes is manageable, this means you can use a sieve to compute all of the 32-bit prime numbers, setting a bit in the map if a number is prime and otherwise leaving the bit 0. On my old Mac Pro computer, it takes hours or less to run the sieve (implemented in C++). Once this is done, you can find the bit nearest to any number and the search up and down in the map to find the nearest prime number to that number. So, trading memory for speed in this way, you can get the nearest prime number to any randomly-chosen number very quickly!
