To wyzwanie jest pierwszym z serii problemów z najmniejszą liczbą operacji , które powinny zostać zapisane w procesorze GOLF . Następny znajdziesz tutaj
Partycja numeru, N
to lista liczb, które się sumują N
. Prime partycja jest lista liczb pierwszych, które dodają do N
.
W przypadku tego wyzwania otrzymujesz jedną liczbę całkowitą N ≥ 2
. Musisz wygenerować możliwie najkrótszą partycję główną N
. Jeśli istnieje wiele możliwych partycji, możesz wydrukować dowolną z nich.
Przykłady:
9: [2, 7]
12: [5, 7]
95: [89, 3, 3]
337: [337]
1023749: [1023733, 13, 3]
20831531: [20831323, 197, 11]
Twój program powinien być napisany w GOLF CPU . Do wejścia / wyjścia można użyć STDIO lub rejestrów. Lista może być w dowolnej kolejności, a jeśli używasz STDOUT, można ją oddzielić białymi spacjami lub przecinkami (bez nawiasów). Oczywiście, twarde kodowanie rozwiązań nie jest dozwolone, ani też nie jest to więcej niż kilka pierwszych liczb pierwszych.
Jest to problem z najmniejszą liczbą operacji , więc wygrywa odpowiedź, która rozwiązuje powyższe przykłady z najmniejszą liczbą cykli!
źródło
Odpowiedzi:
159 326 251 cykli
Wejściowy
n
, wyjściowyr
,s
it
(pomijając zer).Przypadki testowe:
źródło
Cykle ogółem dla przykładów: 477,918,603
Aktualizacja 1: Zaktualizowano, aby użyć hipotezy Lemoine .
Aktualizacja 2: Zaktualizowano, aby używać Sita Eratostenesa zamiast naiwnego znajdowania liczb pierwszych.
Biegnij z:
Przykładowy przebieg:
Liczba cykli na przykład dane wejściowe:
Pierwsze
(N+1)*8
bajty stosu uważamy za tablicę zawierającąN+1
wartości 64-bitowe. (Ponieważ wielkość sterty jest ograniczona, będzie to działać tylko w przypadkuN < 2^57
). Wartość wpisu wi*8
oznacza,i
że liczba pierwsza jest liczbą pierwszą:Kiedy skończymy budować tablicę, będzie to wyglądać
[-1, -1, 3, 5, -1, 7, -1, 11, -1, -1, -1, 13, ...]
.Używamy Sita Eratostenesa do zbudowania tablicy.
Następnie program wykonuje następujące czynności w pseudokodzie:
Gwarantuje to, że zadziała ze względu na hipotezę Lemoine i słabą hipotezę Goldbacha . Hipoteza Lemoine'a nie została jeszcze udowodniona, ale prawdopodobnie dotyczy to liczb poniżej 2 ^ 57.
źródło