VIII Olimpiada Informatyczna 2000/2001
Zadanie: GOL
Autor: Wojciech Guzicki
Gorszy Goldbach
Zawody II stopnia, dzień próbny 6 luty 2001
Plik źródłowy: GOL.??? (np. pas, c, cpp)
Plik wykonywalny: GOL.exe
Plik wejściowy: GOL.in
Plik wyjściowy: GOL.out

W roku 1742 C. Goldbach w liście do L. Eulera napisał, że jego zdaniem każda liczba całkowita n>5 jest sumą trzech liczb pierwszych (Liczba pierwsza to liczba naturalna n>1, która ma tylko dwa dzielniki naturalne: 1 oraz n.). Euler odpisał, że jest to równoważne temu, że każda liczba parzysta n>=4 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 4...1011 (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 n>=10 jest sumą różnych nieparzystych liczb pierwszych. Twoje zadanie polega na napisaniu programu, który:

Takich rozkładów może być wiele. Twój program może znaleźć jakikolwiek z nich.

Wejście

W pierwszym wierszu pliku tekstowego GOL.IN zapisano jedną dodatnią liczbę całkowitą n, n<=40. W każdym z kolejnych n wierszy znajduje się jedna liczba całkowita z przedziału [10,...,2 000 000 000].

Wyjście

Rozkład liczby k musi być zapisany w dwóch wierszach. W pierwszym wierszu należy zapisać jedną liczbę całkowitą m>=1, będącą liczbą składników rozkładu. W drugim wierszu należy zapisać, w rosnącej kolejności, m różnych nieparzystych liczb pierwszych, których suma jest równa k, pooddzielanych pojedynczymi odstępami. Rozkłady powinny występować w kolejności zgodnej z kolejnością liczb w pliku wejściowym.

Przykład

Dla pliku wejściowego GOL.IN: 
2
59
15
poprawną odpowiedzią jest plik wyjściowy GOL.OUT: 
5
5 7 11 17 19
3
3 5 7