¿Cómo crear el mapeo más compacto n → isprime(n) hasta un límite N?
Naturalmente, bool isprime(number)habría una estructura de datos que podría consultar.
Defino que el mejor algoritmo 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.
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 un poco de trabajo, pero los números que terminan en 1, 3, 7 o 9 deben estar presentes en la matriz de bits.
¿Cómo soluciono el problema?
El algoritmo más rápido para pruebas primarias generales es AKS . El artículo de Wikipedia lo describe detalladamente y contiene enlaces al artículo original.
Si quieres encontrar números grandes, busca primos que tengan formas especiales como los primos de Mersenne .
El algoritmo que suelo implementar (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 O(sqrt(N))algoritmo clásico. Utiliza el hecho de que un primo (excepto 2 y 3) tiene la forma 6k - 1o 6k + 1y solo considera los divisores de esta forma.
A veces, si realmente quiero velocidad y el alcance es limitado , implemento una prueba pseudoprincipal basada en el pequeño teorema de Fermat . Si realmente quiero más velocidad (es decir, evitar el algoritmo O(sqrt(N)) por completo), calculo previamente los falsos positivos (consulte los números de Carmichael ) y hago una búsqueda binaria. Esta es, con diferencia, la prueba más rápida que he implementado, el único inconveniente es que el alcance es limitado.
Una solución de fuerza bruta bastante simple y concisa para verificar si un número N es primo: simplemente verifique si hay algún divisor de N desde 2 hasta la raíz cuadrada de N (vea por qué aquí si está interesado).
El siguiente código es compatible tanto con Python 2 como con Python 3:
from math import sqrt
from itertools import count, islice
def is_prime(n):
return n > 1 and all(n % i for i in islice(count(2), int(sqrt(n) - 1)))
Y aquí hay una implementación más simple de Python 3:
def is_prime(n):
return n > 1 and all(n % i for i in range(2, int(n ** 0.5) + 1))
Aquí están las versiones extendidas de lo anterior para mayor claridad:
from math import sqrt
from itertools import count, islice
def is_prime(n):
if n < 2:
return False
for divisor in islice(count(2), int(sqrt(n) - 1)):
if n % divisor == 0:
return False
return True
def is_prime(n):
if n < 2:
return False
for divisor in range(2, int(n ** 0.5) + 1):
if n % divisor == 0:
return False
return True
Esto no pretende ser el algoritmo de verificación de primalidad más rápido ni el más óptimo, solo logra el objetivo de ser simple y conciso, lo que también reduce los errores de implementación. Tiene una complejidad temporal de O(sqrt(n)).
Si buscas algoritmos más rápidos para comprobar si un número es primo, quizás te interese lo siguiente:
- Encontrar números primos y demostrar la primalidad : breve descripción y explicación de las pruebas de primalidad más famosas y su historia.
- Pruebas de primalidad probabilística (Wikipedia) : se pueden incorporar en el código anterior con bastante facilidad para omitir la fuerza bruta si no pasan, como ejemplo está esta excelente respuesta al duplicado de esta pregunta.
- Pruebas primarias deterministas rápidas (Wikipedia)
- Esta pregunta y respuesta es la forma más rápida de enumerar todos los números primos debajo de N junto con la
pyprimesievebiblioteca.
Notas de implementación
Es posible que hayas notado que en la implementación compatible con Python 2 estoy usando itertools.count()en combinación con itertools.islice()en lugar de un simple range()o xrange()(el antiguo rango de generadores de Python 2 , que en Python 3 es el predeterminado). Esto se debe a que en CPython 2 xrange(N)para algún N tal que N > 2 63 ‒ 1 (o N > 2 31 ‒ 1 dependiendo de la implementación) genera un OverflowError. Este es un detalle desafortunado de la implementación de CPython.
Podemos utilizar itertoolspara superar este problema. Dado que estamos contando desde 2hasta el infinito usando itertools.count(2), llegaremos a los pasos sqrt(n)posteriores sqrt(n) - 1y podemos limitar el generador usando itertools.islice().
Hay muchas formas eficientes de probar la primalidad (y esta no es una de ellas), pero el bucle que escribiste se puede reescribir de manera concisa en Python:
def is_prime(a):
return all(a % i for i in xrange(2, a))
Es decir, a es primo si todos los números entre 2 y a (sin incluir) dan un resto distinto de cero cuando se dividen en a.
Nov 07 '2010 13:11
Esta es la forma más eficaz de ver si un número es primo, si sólo tienes unas pocas consultas. Si preguntas a muchos números si son primos, prueba con la Criba de Eratóstenes .
import math
def is_prime(n):
if n == 2:
return True
if n % 2 == 0 or n <= 1:
return False
sqr = int(math.sqrt(n)) + 1
for divisor in range(3, sqr, 2):
if n % divisor == 0:
return False
return True
