Esse desafio é o primeiro de uma série de problemas de menor número de operações que devem ser gravados na CPU do GOLF . Você pode encontrar o próximo aqui
Uma partição de um número,, N
é uma lista de números que somam N
. Uma partição primária é uma lista de números primos que somam N
.
Para esse desafio, você recebe um único número inteiro N ≥ 2
. Você precisa gerar a partição principal mais curta possível N
. Se houver várias partições possíveis, você poderá imprimir qualquer uma delas.
Exemplos:
9: [2, 7]
12: [5, 7]
95: [89, 3, 3]
337: [337]
1023749: [1023733, 13, 3]
20831531: [20831323, 197, 11]
Seu programa deve ser escrito na CPU GOLF . Para entrada / saída, você pode usar o STDIO ou os registradores. A lista pode estar em qualquer ordem e, se você estiver usando STDOUT, pode ser separada por espaços em branco ou vírgulas (sem colchetes). Obviamente, a codificação codificada das soluções não é permitida, nem a codificação codificada é mais do que os primeiros números primos.
Esse é um problema de poucas operações ; portanto, a resposta que resolve os exemplos acima com a menor quantidade de ciclos vence!
fonte
Respostas:
159.326.251 ciclos
De entrada é
n
, a saída ér
,s
et
(ignorando os zeros).Casos de teste:
fonte
Total de ciclos para exemplos: 477.918.603
Atualização 1: Atualizado para usar a conjectura de Lemoine .
Atualização 2: Atualizado para usar a Peneira de Eratóstenes em vez de encontrar ingenuamente os números primos.
Correr com:
Exemplo de execução:
Contagem de ciclos, por exemplo, entrada:
Consideramos os primeiros
(N+1)*8
bytes do heap como uma matriz que contémN+1
valores de 64 bits. (Como o heap é limitado em tamanho, isso funcionará apenasN < 2^57
). O valor da entrada emi*8
indica se o valori
é primo:Quando terminarmos de construir a matriz, será semelhante
[-1, -1, 3, 5, -1, 7, -1, 11, -1, -1, -1, 13, ...]
.Usamos a Peneira de Eratóstenes para construir a matriz.
Em seguida, o programa faz o seguinte em pseudo-código:
É garantido que funcione por causa da conjectura de Lemoine e da fraca conjectura de Goldbach . A conjectura de Lemoine ainda não foi comprovada, mas provavelmente é verdade para números abaixo de 2 ^ 57.
fonte