¿Cuál es el algoritmo más rápido para encontrar números primos?

¿Cuál es el algoritmo más rápido para encontrar números primos usando C ++? ¡He usado el algoritmo de tamiz pero todavía quiero que sea más rápido!

Una implementación muy rápida de Sieve of Atkin es la principal de Dan Bernstein. Este tamiz es más eficiente que el Tamiz de Eratóstenes . Su página tiene información de referencia.

Si tiene que ser realmente rápido, puede incluir una lista de primos:
http://www.bigprimes.net/archive/prime/

Si solo tiene que saber si un determinado número es un número primo, hay varias pruebas principales enumeradas en wikipedia . Probablemente sean el método más rápido para determinar si los números grandes son primos, especialmente porque pueden decirle si un número no es primo.

Él, él, sé que soy una pregunta nigromante que responde a viejas preguntas, pero acabo de encontrar esta pregunta buscando en la red formas de implementar pruebas de números primos eficientes.

Hasta ahora, creo que el algoritmo de prueba de número primo más rápido es Strong Probable Prime (SPRP). Cito de los foros de Nvidia CUDA:

Uno de los problemas de nicho más prácticos en teoría de números tiene que ver con la identificación de números primos. Dado N, ¿cómo se puede determinar de manera eficiente si es primo o no? Esto no es solo un problema treceico, puede ser uno real en el código, tal vez cuando necesite encontrar dinámicamente un tamaño de tabla hash dentro de ciertos rangos. Si N es algo del orden de 2 ^ 30, ¿realmente desea hacer 30000 pruebas de división para buscar algún factor? Obviamente no.

La solución práctica común a este problema es una prueba simple llamada prueba primaria probable de Euler, y una generalización más poderosa llamada Strong Probable Prime (SPRP). Esta es una prueba que para un número entero N puede clasificarlo probabilísticamente como primo o no, y las pruebas repetidas pueden boost la probabilidad de corrección. La parte lenta de la prueba en sí misma implica principalmente calcular un valor similar al módulo A ^ (N-1) N. Cualquiera que implemente variantes de cifrado de clave pública RSA ha utilizado este algoritmo. Es útil tanto para enteros grandes (como 512 bits) como para enteros normales de 32 o 64 bits.

La prueba puede cambiarse de un rechazo probabilístico a una prueba definitiva de primalidad mediante la precomputación de ciertos parámetros de entrada de prueba que se sabe que siempre tienen éxito para rangos de N. Desafortunadamente, el descubrimiento de estas “pruebas más conocidas” es efectivamente una búsqueda de un gran ( de hecho infinito) dominio. En 1980, una primera lista de pruebas útiles fue creada por Carl Pomerance (famoso por ser el factor de RSA-129 con su algoritmo de Seive cuadrático). Más tarde, Jaeschke mejoró los resultados significativamente en 1993. En 2004, Zhang y Tang mejoraron la teoría y límites del dominio de búsqueda. Greathouse y Livingstone han lanzado los resultados más modernos hasta ahora en la web, en http://math.crg4.com/primes.html , los mejores resultados de un gran dominio de búsqueda.

Consulte aquí para obtener más información: http://primes.utm.edu/prove/prove2_3.html y http://forums.nvidia.com/index.php?showtopic=70483

Si solo necesita una forma de generar números primos muy grandes y no le interesa generar todos los números primos

Y si no solo quiere utilizar el algoritmo más rápido sino también el hardware más rápido, intente implementarlo usando Nvidia CUDA, escriba un kernel para CUDA y ejecútelo en GPU.

Incluso puede ganar algo de dinero si descubre números primos lo suficientemente grandes, EFF está otorgando premios de $ 50K a $ 250K: https://www.eff.org/awards/coop

Hay una prueba 100% matemática que verificará si un número P es primo o no, se llama Prueba de Primitivas AKS .

El concepto es simple: dado un número P , si todos los coeficientes de (x-1)^P - (x^P-1) son divisibles por P , entonces P es un número primo; de lo contrario, es un número compuesto.

Por ejemplo, dado P = 3 , daría el polinomio:

  (x-1)^3 - (x^3 - 1) = x^3 + 3x^2 - 3x - 1 - (x^3 - 1) = 3x^2 - 3x 

Y los coeficientes son ambos divisibles por 3 , por lo tanto, el número es primo.

Y un ejemplo donde P = 4 , que NO es un primo cedería:

  (x-1)^4 - (x^4-1) = x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1) = -4x^3 + 6x^2 - 4x 

Y aquí podemos ver que los coeficientes 6 no son divisibles por 4 , por lo tanto, NO es primo.

El polinomio (x-1)^P tendrá P+1 términos y se puede encontrar usando la combinación. Por lo tanto, esta prueba se ejecutará en tiempo de ejecución de O(n) , por lo que no sé qué tan útil sería, ya que simplemente puede iterar sobre i desde 0 a p probar el rest.

¿Tu problema es decidir si un número en particular es primo? Entonces necesitas una prueba de primalidad (fácil). ¿O necesitas todos los números primos hasta un número determinado? En ese caso, los tamices primarios son buenos (fáciles, pero requieren memoria). ¿O necesitas los factores primos de un número? Esto requeriría factorización (difícil para grandes cantidades si realmente quiere los métodos más eficientes). ¿Qué tan grandes son los números que estás viendo? 16 bits? 32 bits? ¿más grande?

Una forma inteligente y eficiente es precomputar tablas de primos y mantenerlos en un archivo utilizando una encoding de nivel de bit. El archivo se considera un vector de bit largo mientras que el bit n representa entero n. Si n es primo, su bit se establece en uno y en cero de lo contrario. La búsqueda es muy rápida (calcula el desplazamiento de bytes y una máscara de bits) y no requiere cargar el archivo en la memoria.

Depende de su aplicación. Hay algunas consideraciones:

  • ¿Necesita solo la información de si algunos números son primos, necesita todos los números primos hasta cierto límite, o necesita (potencialmente) todos los números primos?
  • ¿Qué tan grandes son los números con los que tienes que lidiar?

Las pruebas de Miller-Rabin y analógicas son solo más rápidas que un tamiz para números que superan un cierto tamaño (en algún lugar alrededor de unos pocos millones, creo). Debajo de eso, usar una división de prueba (si solo tienes algunos números) o un tamiz es más rápido.

Rabin-Miller es una prueba de primalidad probabilística estándar. (Lo ejecuta K veces y el número de entrada es definitivamente compuesto, o es probablemente primo con probabilidad de error 4- K . (unos cientos de iteraciones y es casi seguro que le está diciendo la verdad)

Existe una variante no probabilística (determinista) de Rabin Miller .

El Gran Internet Mersenne Prime Search (GIMPS), que ha encontrado el récord mundial de mayor rendimiento comprobado (2 74,207,281 – 1 en junio de 2017), utiliza varios algoritmos , pero estos son primos en formas especiales. Sin embargo, la página anterior de GIMPS incluye algunas pruebas generales de primalidad determinista. Parecen indicar que el algoritmo es “más rápido” depende del tamaño del número que se probará. Si su número cabe en 64 bits, entonces probablemente no deba usar un método destinado a trabajar en números primos de varios millones de dígitos.

Siempre utilizo este método para calcular los números primos que siguen con el algoritmo de tamiz.

 void primelist() { for(int i = 4; i < pr; i += 2) mark[ i ] = false; for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true; for(int i = 3, sq = sqrt( pr ); i < sq; i += 2) if(mark[ i ]) for(int j = i << 1; j < pr; j += i) mark[ j ] = false; prime[ 0 ] = 2; ind = 1; for(int i = 3; i < pr; i += 2) if(mark[ i ]) ind++; printf("%d\n", ind); } 
 #include main() { long long unsigned x,y,b,z,e,r,c; scanf("%llu",&x); if(x<2)return 0; scanf("%llu",&y); if(y0)z=3; } if(e==0) { printf("|%llu",z); r+=1; } } printf("|\n%llu outputs...\n",r); scanf("%llu",&r); } 
 #include  using namespace std; int set [1000000]; int main (){ for (int i=0; i<1000000; i++){ set [i] = 0; } int set_size= 1000; set [set_size]; set [0] = 2; set [1] = 3; int Ps = 0; int last = 2; cout << 2 << " " << 3 << " "; for (int n=1; n<10000; n++){ int t = 0; Ps = (n%2)+1+(3*n); for (int i=0; i==i; i++){ if (set [i] == 0) break; if (Ps%set[i]==0){ t=1; break; } } if (t==0){ cout << Ps << " "; set [last] = Ps; last++; } } //cout << last << endl; cout << endl; system ("pause"); return 0; } 

Sé que es un poco más tarde, pero esto podría ser útil para las personas que llegan aquí desde las búsquedas. De todos modos, aquí hay algo de JavaScript que se basa en el hecho de que solo se deben probar los factores primos, por lo que los primos anteriores generados por el código se vuelven a usar como factores de prueba para los posteriores. Por supuesto, todos los valores pares y mod 5 se filtran primero. El resultado estará en la matriz P, y este código puede procesar 10 millones de primos en menos de 1,5 segundos en una PC i7 (o 100 millones en aproximadamente 20). Reescrito en C debería ser muy rápido.

 var P = [1, 2], j, k, l = 3 for (k = 3 ; k < 10000000 ; k += 2) { loop: if (++l < 5) { for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j) if (k % P[j] == 0) break loop P[P.length] = k } else l = 0 } 
 #include using namespace std; void main() { int num,i,j,prime; cout<<"Enter the upper limit :"; cin>>num; cout<<"Prime numbers till "<