Random Primes between 4000000000 and 4294967291 (C++)

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.