¿Qué es un hogar prime?
Por ejemplo, tome HP (4). Primero, encuentra los factores primos. Los factores primos de 4 ( en orden numérico de menor a mayor, siempre ) son 2, 2. Tome esos factores como un número literal. 2, 2 se convierte en 22. Este proceso de factorización continúa hasta llegar a un número primo.
number prime factors
4 2, 2
22 2, 11
211 211 is prime
Una vez que alcanzas un número primo, la secuencia termina. HP (4) = 211. Aquí hay un ejemplo más largo, con 14:
number prime factors
14 2, 7
27 3, 3, 3
333 3, 3, 37
3337 47, 71
4771 13, 367
13367 13367 is prime
Su desafío es crear un programa que calcule HP (x) dado x, y hacerlo lo más rápido posible . Puede usar cualquier recurso que desee, que no sea una lista de primos domésticos conocidos.
Tome nota, estos números se vuelven muy grandes muy rápido. En x = 8, HP (x) salta a 3331113965338635107. HP (49) aún no se ha encontrado.
La velocidad del programa se probará en una Raspberry Pi 2, promediando las siguientes entradas:
16
20
64
65
80
Si tiene una Raspberry Pi 2, programe el programa usted mismo y luego promedie los tiempos.
fuente
Respuestas:
Mathematica, HP (80) en ~ 0.88s
Función anónima. Toma un número como entrada y devuelve un número como salida.
fuente
1
final no debería estar allí ...CompositeQ
para!PrimeQ
(que también asegura que su respuesta no se repita para siempre en la entrada1
).HP(80)
en tan poco tiempo sin tener los números primos codificados en alguna parte? Mi computadora portátil i7 está tardando horas en realizar una verificación de primalidad, así como en encontrar los factores primos, paraHP(80)
cuando llegue47109211289720051
.PyPy 5.4.1 64bit (linux), HP (80) ~ 1.54s
La versión de 32 bits será un poco más lenta.
Utilizo cuatro métodos de factorización diferentes, con puntos de corte determinados empíricamente:
Intenté por un tiempo encontrar una ruptura limpia entre ECF y MPQS, pero no parece haber una. Sin embargo, si n contiene un factor pequeño, ECF generalmente lo encontrará casi de inmediato, por lo que opté por probar solo unas pocas curvas, antes de pasar a MPQS.
Actualmente, es solo ~ 2 veces más lento que Mathmatica, lo que sin duda considero un éxito.
home-prime.py
Tiempos de muestra
El promedio de los 5 es de aproximadamente 0.39s.
Dependencias
mpqs.py
se toma directamente de mi respuesta a la factorización semiprime más rápida con algunas modificaciones muy menores.mpqs.py
my_math.py
está tomado de la misma publicación quempqs.py
, sin embargo, también he agregado el generador de números primos ilimitados que utilicé en mi respuesta para encontrar la brecha más grande entre los números primos buenos .my_math.py
fuente
Python 2 + primefac 1.1
No tengo un Raspberry Pi para probarlo.
Pruébalo en línea
La
primefac
función devuelve una lista de todos los factores primos den
. En su definición, llamaisprime(n)
, que utiliza una combinación de división de prueba, método de Euler y la prueba de primalidad de Miller-Rabin. Recomiendo descargar el paquete y ver la fuente.Intenté usar en
n = n * 10 ** int(floor(log10(f))+1) + f
lugar de la concatenación de cadenas, pero es mucho más lento.fuente
pip install primefac
funcionó para mí, aunque 65 y 80 no parecen ejecutarse en Windows, debido a que estáfork
en segundo plano.primefac
fue bastante divertido, ya que hay muchos comentarios conTODO
ofind out why this is throwing errors
# This occasionally throws IndexErrors.
Sí, porque eliminó la verificación de que hay más suavizadores que factores primos utilizados.DO#
Esta es una versión más optimizada del código anterior, con algunas partes redundantes innecesarias eliminadas.
Salida (en mi computadora portátil i7):
Prueba en línea
fuente
Perl + ntheory, HP (80) en 0.35s en PC
No Raspberry Pi en la mano.
La prueba de primalidad es ES BPSW, más un único MR de base aleatoria para números más grandes. A este tamaño podríamos usar
is_provable_prime
(n-1 y / o ECPP) sin una diferencia notable en la velocidad, pero eso cambiaría para valores de> 300 dígitos sin beneficio real. El factoring incluye prueba, potencia, Rho-Brent, P-1, SQUFOF, ECM, QS según el tamaño.Para estas entradas, funciona aproximadamente a la misma velocidad que el código Charles 'Pari / GP en el sitio OEIS. ntheory tiene un factoring más rápido para números pequeños, y mi P-1 y ECM son bastante buenos, pero el QS no es excelente, por lo que esperaría que Pari sea más rápido en algún momento.
fuente
use feature "say";
.