Gorszy Goldbach
Limit pamięci: 32 MB
W roku 1742 C. Goldbach w liście do L. Eulera napisał,
że jego zdaniem każda liczba całkowita jest sumą
trzech liczb pierwszych
(liczba pierwsza to liczba naturalna , która ma tylko
dwa dzielniki naturalne: 1 oraz ).
Euler odpisał, że jest to równoważne temu, że każda
liczba parzysta jest sumą dwóch liczb pierwszych.
To jednak nie przybliżyło ich do rozwiązania podstawowego problemu:
czy tak jest naprawdę.
Dziś wiemy, że jest tak dla liczb
aż do (wiemy też dużo więcej, ale
cała hipoteza jest nadal problemem otwartym).
Nie będziemy tego sprawdzać, postawimy sobie mniej ambitne zadanie.
Okazuje się, że każda liczba naturalna jest sumą różnych
nieparzystych liczb pierwszych.
Twoje zadanie polega na napisaniu programu, który:
-
wczyta ze standardowego wejścia liczby całkowite,
-
znajdzie ich rozkłady na sumy różnych nieparzystych liczb pierwszych,
-
wypisze wyniki na standardowe wyjście.
Takich rozkładów może być wiele.
Twój program może znaleźć jakikolwiek z nich.
Wejście
W pierwszym wierszu standardowego wejścia zapisano jedną
dodatnią liczbę całkowitą , . W każdym z kolejnych
wierszy znajduje się jedna liczba całkowita z przedziału
.
Wyjście
Rozkład liczby musi być zapisany w dwóch wierszach standardowego wyjścia.
W pierwszym wierszu należy zapisać jedną liczbę całkowitą ,
będącą liczbą składników rozkładu.
W drugim wierszu należy zapisać, w rosnącej kolejności,
różnych nieparzystych liczb pierwszych,
których suma jest równa , pooddzielanych pojedynczymi odstępami.
Rozkłady powinny występować w kolejności zgodnej z kolejnością liczb
na wejściu.
Przykład
Dla danych wejściowych:
2
59
15
poprawną odpowiedzią jest:
5
5 7 11 17 19
3
3 5 7
Autorzy zadania: Wojciech Guzicki, Jarosław Wróblewski.