Este desafío es el primero de una serie de pocos problemas de operaciones que deberían escribirse en la CPU GOLF . Puedes encontrar el siguiente aquí
Una partición de un número, N
es una lista de números que se suman N
. Una partición prima es una lista de números primos que se suman N
.
Para este desafío, se le da un solo número entero N ≥ 2
. Necesita generar la partición primaria más corta posible para N
. Si hay varias particiones posibles, puede imprimir cualquiera de ellas.
Ejemplos:
9: [2, 7]
12: [5, 7]
95: [89, 3, 3]
337: [337]
1023749: [1023733, 13, 3]
20831531: [20831323, 197, 11]
Su programa debe estar escrito en la CPU GOLF . Para entrada / salida puede usar STDIO o los registros. La lista puede estar en cualquier orden, y si está usando STDOUT, puede separarse por espacios en blanco o comas (no se necesitan corchetes). Obviamente, codificar las soluciones no está permitido, ni codificar más que los primeros números primos.
Este es un problema de pocas operaciones , por lo que gana la respuesta que resuelve los ejemplos anteriores con la menor cantidad de ciclos.
fuente
Respuestas:
159,326,251 ciclos
De entrada es
n
, de salida esr
,s
yt
(ignorando los ceros).Casos de prueba:
fuente
Ciclos totales por ejemplos: 477,918,603
Actualización 1: Actualizado para usar la conjetura de Lemoine .
Actualización 2: Actualizado para usar el Tamiz de Eratóstenes en lugar de encontrar ingenuamente los números primos.
Corre con:
Ejemplo de ejecución:
Recuento de ciclos, por ejemplo, entrada:
Consideramos que los primeros
(N+1)*8
bytes del montón son una matriz que contieneN+1
valores de 64 bits. (Como el montón es de tamaño limitado, esto solo funcionaráN < 2^57
). El valor de la entrada eni*8
indica sii
es primo:Cuando hayamos terminado de construir la matriz, se verá así
[-1, -1, 3, 5, -1, 7, -1, 11, -1, -1, -1, 13, ...]
.Usamos el Tamiz de Eratóstenes para construir la matriz.
A continuación, el programa hace lo siguiente en pseudocódigo:
Esto está garantizado para funcionar debido a la conjetura de Lemoine y la conjetura débil de Goldbach . La conjetura de Lemoine aún no se ha probado, pero probablemente sea cierto para números inferiores a 2 ^ 57.
fuente