son saber que primos primo para numeros numero los ejemplos definicion cuales compuestos como cien calcular c++ algorithm primes

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



numeros primos del 1 al 100 (12)

É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 aumentar 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 <un entero n, puede usar la prueba de Lucas-Lehmer para verificar los números primos de Mersenne. Un número primo de Mersenne tiene la forma de 2 ^ p -1. Creo que la prueba de Lucas-Lehmer es el algoritmo más rápido descubierto para los números primos de Mersenne.

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

¿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!

¿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 codificación 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.

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 }

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

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.

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.

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 resto.

#include <iostream> 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; }

#include<iostream> using namespace std; void main() { int num,i,j,prime; cout<<"Enter the upper limit :"; cin>>num; cout<<"Prime numbers till "<<num<<" are :2, "; for(i=3;i<=num;i++) { prime=1; for(j=2;j<i;j++) { if(i%j==0) { prime=0; break; } } if(prime==1) cout<<i<<", "; } }

#include<stdio.h> main() { long long unsigned x,y,b,z,e,r,c; scanf("%llu",&x); if(x<2)return 0; scanf("%llu",&y); if(y<x)return 0; if(x==2)printf("|2"); if(x%2==0)x+=1; if(y%2==0)y-=1; for(b=x;b<=y;b+=2) { z=b;e=0; for(c=2;c*c<=z;c++) { if(z%c==0)e++; if(e>0)z=3; } if(e==0) { printf("|%llu",z); r+=1; } } printf("|/n%llu outputs.../n",r); scanf("%llu",&r); }