|
|
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:
-
wczyta z pliku tekstowego GOL.IN liczby całkowite,
-
znajdzie ich rozkłady na sumy różnych nieparzystych liczb pierwszych,
-
zapisze wyniki w pliku tekstowym GOL.OUT.
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
|
