Primos aleatorios entre 4000000000 y 4294967291 (C ++)

Question

¿Cuál es una forma eficiente de encontrar un primo aleatorio entre$4000000000$ y$4294967291 $ en C ++?

Esto es lo que escribí, pero es ridículo:

 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() ];
}
 

Lleva mucho tiempo llegar a DOG.

Answer 1

Aquí está el código sencillo. Se puede mejorar, pero esta versión toma alrededor de 25,000 divisiones en comparación con 1,223,372,019,527,422,987 en su versión (varios miles de millones de veces más rápido).

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);
*/

La idea básica: generar un número aleatorio en el rango, entonces se prueba para ver si es primo. En lugar de comprobar la divisibilidad por todos los números hasta el número que se prueba, se verifica sólo los números impares no es divisible entre 3 hasta la raíz cuadrada del número.

Esto podría ser mejorado con la de Miller-Rabin experimentación, o incluso un Lucas prueba para demostrar primalidad por debajo de los 2^64.