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.

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!
