La tarea es encontrar un factor no trivial de un número compuesto.
Escriba código que encuentre un factor no trivial de un número compuesto lo más rápido posible, siempre que su código no tenga más de 140 bytes de longitud. La salida debería ser el factor que ha encontrado.
Su código puede tomar entrada y dar salida de cualquier manera que sea conveniente, incluyendo, por ejemplo, argumentos para una función.
Casos de prueba que enumeran todos los factores (solo necesita generar uno)
187: 11 17
1679: 23 73
14369648346682547857: 1500450271 9576890767
34747575467581863011: 3628273133 9576890767
52634041113150420921061348357: 2860486313 5463458053 3367900313
82312263010898855308580978867: 264575131106459 311111111111113
205255454905325730631914319249: 2860486313 71755440315342536873
1233457775854251160763811229216063007: 1110111110111 1000000000063 1111111999999
1751952685614616185916001760791655006749: 36413321723440003717 48112959837082048697
No calificaré su respuesta en el siguiente caso de prueba difícil que puede ser de interés para la prueba:
513231721363284898797712130584280850383: 40206835204840513073 12764787846358441471
Puntuación
Su puntaje es el tiempo combinado para factorizar todos los casos de prueba anteriores con una penalización de 10 minutos por cada factorización fallida (todo redondeado al segundo más cercano). Su código también debería funcionar para otros enteros, eso no solo debería codificar estas respuestas.
Dejaré su código después de 10 minutos.
Si dos personas obtienen el mismo puntaje, la primera respuesta gana.
Restricciones
Su código no puede usar ninguna función incorporada o de biblioteca que realice la factorización de enteros. Puede suponer que la entrada toma menos de 256 bits. Todos los números de entrada serán compuestos.
¿Cómo voy a cronometrar?
Literalmente, ejecutaré time ./myprog
en mi sistema Ubuntu para hacer el cronometraje, así que también proporcione un programa completo para que ejecute que incluya cualquier función que haya definido.
Una nota para idiomas compilados
El tiempo de compilación no debe tomar más de 1 minuto en mi máquina.
¿Es realmente posible?
Si ignora las restricciones de espacio, cada una de ellas puede factorizarse en menos de 2 segundos en mi computadora usando código Python puro + pypy.
Entonces, ¿qué es un algoritmo de factorización no trivial?
El algoritmo rho de Pollard es rápido y adecuado para jugar al golf. Por supuesto, también hay muchas otras formas de factorizar un número entero .
Aún más rápido es el tamiz cuadrático . Parece un desafío serio exprimir eso en 140 bytes.
Puntajes principales
- SEJPM , 10 minutos de penalización por el último caso de prueba + 16 segundos en Haskell
2 ** 1024
?2
o2, 2
?Respuestas:
Haskell,
100979189877267 Bytes¡Pruébelo en línea!
-3 bytes gracias a @flawr
-6 bytes gracias a @flawr nuevamente
-2 bytes gracias a @flawr una vez más
-2 bytes gracias a un conjunto optimizado de parámetros
-1 byte gracias a @flawrs otra vez
-14 bytes gracias al requisito a solo tener que generar un factor
-5 bytes gracias a @AndersKaseorg
Esto funciona para los primeros 5 casos de prueba en un tiempo imperceptible.
Esto probablemente superará el tiempo en el caso de prueba más grande.
En general, esto generalmente devolverá un factor no trivial en el tiempo proporcional a la raíz cuadrada del factor más pequeño.
No funcionará en todas las entradas porque no varía el polinomio y la detección del caso excepcional es difícil de hacer en 140 bytes.
Tampoco generará la factorización completa, sino más bien un factor no trivial y la división de la entrada por este factor.
Tampoco ordenará los factores por tamaño.
El método utilizado es Factorización de Pollard-Rho con el valor inicial estándar de 2 (con el
x^2+1
polinomio estándar aplicado una vez) y el factor constante polinómico no estándar de 7 (porque1
no funcionó con 1679) para todas las evaluaciones posteriores.Programa completo (
factor.hs
):Compilar como
$ ghc factor.hs
(necesitaghc
instalarse).Corre como
$ ./factor <number>
.Ejemplo de ejecución:
Código sin golf:
Calcula el factor no trivial llamando
g
con valores iniciales. El polinomio se aplica previamente en 2 aquí y se vuelve a aplicar en el resultado (5) para que la entrada ag
(en una cláusula "where" ) siempre se pueda usar fácilmente para la prueba gcd.g
(la versión con golf usa infijo#
) luego intenta calcular un factor no triviald
(en la cláusula where en la versión sin golf, en línea en la versión con golf) como la diferencia entre las dos entradasg
, si tiene éxito devuelve dicho factor de lo contrario, vuelve a intentarlo. Aquí puede generarn
como salida sia==b
y, por lo tanto, devuelve solo un factor trivial, el enfoque adecuado para manejar esto sería variar los valores iniciales en este evento o cambiar el polinomio.fuente
|1<2=s a#(s$s b)
podría ser reemplazado con|c<-s b=s a#s c
pienso :): (también ¿por qué no se contabiliza un TIO enlace?)abs
, yab
que siempre es no negativo. (Quizás quisiste decirabs$b-a
, perogcd
acepta argumentos negativos y siempre produce un resultado no negativo). ¡Eso reduce esto a menos de medio tuit!Pari / GP , 137 bytes, ~ 5 segundos
Usando las operaciones de curva elíptica incorporadas de GP (y algunos ajustes de parámetros poco claros) :
ecm
es una función que (debería) devolver un factor. Pruébalo en línea!Prueba:
Sin golf:
Lamentablemente, manejar los factores 2 y 3 usa muchos bytes. Bytes que podrían haberse usado para agregar una etapa 2:
fuente
Axioma, 137 bytes 9 minutos
arriba de la función p () que implementaría algo p-1 para factorizar debajo de qué copiar en un archivo para probar en la función p ()
resultados aquí:
fuente
Axioma, 10 minutos + 31 segundos
z () es la función rho, una función de 137 bytes; ungolfed z () y llamarlo como rho (). Supondría que gcd (0, n) = n, por lo que el ciclo se detiene y regresa para fallar n.
los resultados (z () están bien para todos, pero el último número 1751952685614616185916001760791655006749 no se tienen en cuenta (10 minutos))
fuente
Python 3 ,
10099 bytes,45 4039 segundos + 10 minutos de penalizaciónPruébalo en línea!
Utiliza Pollard-Rho con valor inicial 2 y polinomio x ^ 2 + 1.
fuente
pow
(con el tercer argumento) para mejorar su velocidad de ejecución.