¿Cuál es el mejor algoritmo para verificar si un número es primo?

Solo un ejemplo de lo que estoy buscando: podría representar cada número impar con un bit, por ejemplo, para el rango de números dado (1, 10), comienza en 3:

1110 

El siguiente diccionario se puede exprimir más ¿no? Podría eliminar múltiplos de cinco con algún trabajo, pero los números que terminan con 1, 3, 7 o 9 deben estar allí en la matriz de bits. Espero que esto aclare lo que quiero.

Estoy buscando el mejor algoritmo, para verificar si un número es primordial, es decir, una función booleana:

 bool isprime(number); 

Me gustaría saber el mejor algoritmo para implementar esta funcionalidad. Naturalmente, habría una estructura de datos que podría consultar. Defino el mejor algoritmo , que es el algoritmo que produce una estructura de datos con el menor consumo de memoria para el rango (1, N), donde N es una constante.

Hay muchas maneras de hacer la prueba de primalidad .

Realmente no hay una estructura de datos para que usted pueda consultar. Si tiene muchos números para evaluar, probablemente debería ejecutar una prueba probabilística ya que estos son más rápidos, y luego hacer un seguimiento con una prueba determinista para asegurarse de que el número sea primo.

Debe saber que la matemática detrás de los algoritmos más rápidos no es para los débiles de corazón.

El algoritmo más rápido para la prueba de primo general es AKS . El artículo de Wikipedia lo describe extensamente y enlaces al documento original.

Si quieres encontrar números grandes, mira en primos que tienen formas especiales como primos de Mersenne .

El algoritmo que generalmente implemento (fácil de entender y codificar) es el siguiente (en Python):

 def isprime(n): """Returns True if n is prime.""" if n == 2: return True if n == 3: return True if n % 2 == 0: return False if n % 3 == 0: return False i = 5 w = 2 while i * i <= n: if n % i == 0: return False i += w w = 6 - w return True 

Es una variante del clásico algoritmo O(sqrt(N)) . Utiliza el hecho de que un primo (excepto 2 y 3) tiene la forma 6k - 1 o 6k + 1 y solo mira los divisores de esta forma.

A veces, si realmente quiero velocidad y el rango es limitado , implemento una prueba de pseudoprima basada en el pequeño teorema de Fermat . Si realmente quiero más velocidad (es decir, evito el algoritmo O (sqrt (N)) por completo), precomputo los falsos positivos (vea los números de Carmichael ) y realizo una búsqueda binaria. Esta es, de lejos, la prueba más rápida que he implementado, el único inconveniente es que el scope es limitado.

El mejor método, en mi opinión, es usar lo que se ha ido antes.

Hay listas de los primeros N primos en Internet con N extendiéndose hasta por lo menos cincuenta millones . Descarga los archivos y úsalos, es probable que sea mucho más rápido que cualquier otro método que se te ocurra.

Si desea un algoritmo real para hacer sus propios números primos, Wikipedia tiene todo tipo de cosas buenas en los números primos aquí , incluidos enlaces a los diversos métodos para hacerlo, y las pruebas principales aquí , ambos métodos basados ​​en la probabilidad y deterministas rápidos.

Debería haber un esfuerzo concertado para encontrar los primeros mil millones (o incluso más) de números primos y publicarlos en la red en alguna parte para que la gente pueda dejar de hacer este mismo trabajo una y otra vez y … 🙂

Según la wikipedia, el tamiz de Eratóstenes tiene complejidad O(n * (log n) * (log log n)) y requiere memoria O(n) , por lo que es un buen lugar para comenzar si no se está probando especialmente grande números.

 bool isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n%2 == 0 || n%3 == 0) return false; for (int i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return false; return true; } this is just c++ implementation of above AKS algorithm 

https://en.wikipedia.org/wiki/AKS_primality_test

En Python 3:

 def is_prime(a): if a < 2: return False elif a!=2 and a % 2 == 0: return False else: return all (a % i for i in range(3, int(a**0.5)+1) ) 

Explicación: Un número primo es un número solo divisible por sí mismo y 1. Ej .: 2,3,5,7 ...

1) si a <2: si "a" es menor que 2, no es un primo.

2) elif a! = 2 y a% 2 == 0: si "a" es divisible por 2, entonces definitivamente no es un primo. Pero si a = 2 no queremos evaluar eso ya que es un número primo. De ahí la condición a! = 2

3) devuelve todo (a% i para i en rango (3, int (a 0.5) +1)): ** Primero mira lo que hace all () comando en python. Comenzando desde 3, dividimos "a" hasta su raíz cuadrada (a ** 0.5). Si "a" es divisible, la salida será False. ¿Por qué raíz cuadrada? Digamos a = 16. La raíz cuadrada de 16 = 4. No es necesario evaluar hasta el 15. Solo necesitamos verificar hasta 4 para decir que no es un número primo.

Extra: un bucle para encontrar todo el número primo dentro de un rango.

 for i in range(1,100): if is_prime(i): print("{} is a prime number".format(i) ) 

Python 3:

 def is_prime(a): return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1)) 

Demasiado tarde para la fiesta, pero espero que esto ayude. Esto es relevante si estás buscando grandes números primos:

Para probar números impares grandes, debe usar la prueba Fermat y / o la prueba Miller-Rabin.

Estas pruebas usan una exponenciación modular que es bastante costosa, para la exponenciación de n bits se necesita al menos n una multiplicación grande y n gran división interna. Lo que significa que la complejidad de la exponenciación modular es O (n³).

Entonces, antes de usar las armas grandes, debes hacer bastantes divisiones de prueba. Pero no lo hagas ingenuamente, hay una forma de hacerlo rápido. Primero multiplica tantos primos juntos como tantos ajustes en las palabras que usas para los enteros grandes. Si usa palabras de 32 bits, multiplique 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 3234846615 y calcule el mayor divisor común con el número que prueba usando el algoritmo euclidiano. Después del primer paso, el número se reduce por debajo del tamaño de la palabra y continúa el algoritmo sin realizar divisiones enteras grandes y completas. Si el GCD! = 1, eso significa que uno de los números primos que multiplicaste juntos divide el número, por lo que tienes una prueba de que no es primo. Luego continúe con 31 * 37 * 41 * 43 * 47 = 95041567, y así sucesivamente.

Una vez que haya probado varios cientos (o miles) de primos de esta forma, puede hacer 40 rondas de la prueba de Miller-Rabin para confirmar que el número es primordial, después de 40 rondas puede estar seguro de que el número es primo; solo hay 2 ^ -80 de posibilidades de que sea no (es más probable que su hardware no funcione correctamente …).

Tengo una función principal que funciona hasta (2 ^ 61) -1 Aquí:

 from math import sqrt def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1))) 

Explicación:

La función all() se puede redefinir a esto:

 def all(variables): for element in variables: if not element: return False return True 

La función all() simplemente pasa por una serie de bools / números y devuelve False si ve 0 o False .

La función sqrt() simplemente está haciendo la raíz cuadrada de un número.

Por ejemplo:

 >>> from math import sqrt >>> sqrt(9) >>> 3 >>> sqrt(100) >>> 10 

La parte num % x devuelve el rest de num / x.

Finalmente, range(2, int(sqrt(num))) significa que creará una lista que comienza en 2 y termina en int(sqrt(num)+1)

Para obtener más información sobre el scope, ¡eche un vistazo a este sitio web !

La parte num > 1 solo está comprobando si la variable num es mayor que 1, porque 1 y 0 no se consideran números primos.

Espero que esto haya ayudado 🙂

En Python:

 def is_prime(n): return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1)) 

Una conversión más directa del formalismo matemático a Python usaría todo (n% p! = 0 …) , pero eso requiere una evaluación estricta de todos los valores de p. La versión no puede finalizar anticipadamente si se encuentra un valor True.

Idea similar al algoritmo AKS que se ha mencionado

 public static boolean isPrime(int n) { if(n == 2 || n == 3) return true; if((n & 1 ) == 0 || n % 3 == 0) return false; int limit = (int)Math.sqrt(n) + 1; for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) { if(n % i == 0) return false; numChecks++; } return true; } 

Para saber si el número o los números en un rango son / son primos.

 #!usr/bin/python3 def prime_check(*args): for arg in args: if arg > 1: # prime numbers are greater than 1 for i in range(2,arg): # check for factors if(arg % i) == 0: print(arg,"is not Prime") print(i,"times",arg//i,"is",arg) break else: print(arg,"is Prime") # if input number is less than # or equal to 1, it is not prime else: print(arg,"is not Prime") return # Calling Now prime_check(*list(range(101))) # This will check all the numbers in range 0 to 100 prime_check(#anynumber) # Put any number while calling it will check. 
 myInp=int(input("Enter a number: ")) if myInp==1: print("The number {} is neither a prime not composite no".format(myInp)) elif myInp>1: for i in range(2,myInp//2+1): if myInp%i==0: print("The Number {} is not a prime no".format(myInp)) print("Because",i,"times",myInp//i,"is",myInp) break else: print("The Number {} is a prime no".format(myInp)) else: print("Alas the no {} is a not a prime no".format(myInp)) 

mejor algoritmo para el número de Primes javascript

  function isPrime(num) { if (num <= 1) return false; else if (num <= 3) return true; else if (num % 2 == 0 || num % 3 == 0) return false; var i = 5; while (i * i <= num) { if (num % i == 0 || num % (i + 2) == 0) return false; i += 6; } return true } 

Uno puede usar Sympy .

 import sympy sympy.ntheory.primetest.isprime(33393939393929292929292911111111) True 

De Sympy Doc. El primer paso es buscar factores triviales, que si se encuentran permiten un retorno rápido. Luego, si el tamiz es lo suficientemente grande, use la búsqueda de bisección en el tamiz. Para números pequeños, un conjunto de pruebas determinísticas de Miller-Rabin se realizan con bases que se sabe que no tienen contraejemplos en su rango. Finalmente, si el número es mayor que 2 ^ 64, se realiza una fuerte prueba BPSW. Si bien esta es una prueba principal probable y creemos que existen contraejemplos, no se conocen contraejemplos

Memoria más pequeña? Esto no es el más pequeño, pero es un paso en la dirección correcta.

 class PrimeDictionary { BitArray bits; public PrimeDictionary(int n) { bits = new BitArray(n + 1); for (int i = 0; 2 * i + 3 <= n; i++) { bits.Set(i, CheckPrimality(2 * i + 3)); } } public PrimeDictionary(IEnumerable primes) { bits = new BitArray(primes.Max()); foreach(var prime in primes.Where(p => p != 2)) { bits.Set((prime - 3) / 2, true); } } public bool IsPrime(int k) { if (k == 2) { return true; } if (k % 2 == 0) { return false; } return bits[(k - 3) / 2]; } } 

Por supuesto, debe especificar la definición de CheckPrimality .

Creo que uno de los más rápidos es mi método que hice.

 void prime(long long int number) { // Establishing Variables long long int i = 5; int w = 2; const long long int lim = sqrt(number); // Gets 2 and 3 out of the way if (number == 1) { cout << number << " is hard to classify. \n"; return; } if (number == 2) { cout << number << " is Prime. \n"; return; } if (number == 3) { cout << number << " is Prime. \n"; return; } // Tests Odd Ball Factors if (number % 2 == 0) { cout << number << " is not Prime. \n"; return; } if (number % 3 == 0) { cout << number << " is not Prime. \n"; return; } while (i <= lim) { if (number % i == 0) { cout << number << " is not Prime. \n"; return; } // Tests Number i = i + w; // Increments number w = 6 - i; // We already tested 2 and 3 // So this removes testing multepules of this } cout << number << " is Prime. \n"; return; } 
 public static boolean isPrime(int number) { if(number < 2) return false; else if(number == 2 || number == 3) return true; else { for(int i=2;i<=number/2;i++) if(number%i == 0) return false; else if(i==number/2) return true; } return false; }