Hipoteza Goldbacha

Cześć! Mam do rozwiązania takie zadanie:

Hipoteza Goldbacha to jedno z najstarszych nierozstrzygniętych twierdzeń teorii liczb. Sformułowana została w
XVIII wieku i sprowadza się do twierdzenia, że każdą parzystą liczbę naturalną większą od 4 można przedstawić
jako sumę dwóch nieparzystych liczb pierwszych (niekoniecznie różnych). Na przykład 10 = 7 + 3, 12 = 7 + 5,
20 = 13 + 7 = 17 + 3 itd. Jak widać, czasem istnieje więcej sposobów rozłożenia danej liczby. Jednak do tej pory
nikomu nie udało się udowodnić tego twierdzenia, ani go obalić.
Napisz program, który czyta liczby naturalne i rozkłada je na sumę dwóch liczb pierwszych.

Wejście:
Pierwszy wiersz danych zawiera liczbę całkowitą n (1 ≤ n ≤ 1000) oznaczającą ilość liczb do wczytania. Każdy
z następnych n wierszy zawiera parzystą liczbę naturalną z zakresu od 6 do miliarda.

Wyjście:
Program powinien dla każdej wprowadzonej liczby wypisać wiersz tekstu zawierający dwie liczby pierwsze,
których suma jest równa danej liczbie. Liczby należy wypisać w kolejności niemalejącej i oddzielić od siebie
pojedynczym odstępem. Jeśli istnieje więcej niż jedno rozwiązanie, wtedy należy wypisać parę liczb o
najmniejszej różnicy.

Przykład:
Dla danych wejściowych:
3
20
200
2000
program powinien wypisać:
7 13
97 103
991 1009

Mógłbym mi ktoś pomóc z rozwiązaniem? Nie mam żadnego pomysłu, ponieważ wszelkie sita itd. odpadają ze względu na ogromny zakres danych (od 6 do miliarda).

Ile pamięci możesz użyć?

Nie mam podane, ale pewnie 64MB. Limit czasu pewnie też jest całkiem spory, do 5-6 sekund.

Jedyne na co wpadłem to zrobienie właśnie sita, spisanie liczb pierwszych i szukanie od środka dwóch takich, które dają w sumie to co mają dać.'
Sito dla 10^9 liczb można zrobić na <128MB używając bitset (na 2,4GHz sito dało wynik w ~30sek) + 200MB na te liczby pierwsze.
Pomysł zdecydowanie odpada przy takich ograniczeniach. Zastanawiam się czy jest w ogóle jakaś lepsza możliwość.
Nie wydaje mi się, aby była jakaś inna możliwość niż brute-force, a do niej potrzebna jest lista liczb pierwszych w tym zakresie, a najlepszy algorytm na sporządzenie takiej to sito.
No nic, może ktoś mnie, mam nadzieję, wyprowadzi z błędu.

Ja bym do tego podszedł trochę inaczej bo zauważcie że my wcale nie potrzebujemy robić zwykłego sita. Nie interesuje nad na dobrą sprawę uniwersum wszystkich liczb pierwszych, tylko taka para która da nam spodziewaną sumę. W efekcie testujemy sobie za każdym razem od razu obie liczby, co dość mocno ogranicza obliczenia, szczególnie dla przypadków skrajnych, tzn np. 999999997 + 3 bo wystarczy wykluczyć jedną z liczb.

jako, że miliard jest dość dużą wartością ograniczającą, to sprawdzanie podziału przez wszystkie liczby pierwsze nie ma senesu. To jest zbyt czasochłonne. Samo generowanie sita, znacznie przekroczy limit czasowy.
Najrozsądniej jest zastosować test Millera-Rabina, dla wartości a = 2, 7 i 61 bo tyle wystarczy by tym testem jednoznacznie stwierdzić, że liczba jest pierwsza dla wartości n<4,759,123,141.
Czyli dzielisz liczbę na dwie połówki i sprawdzasz czy obie połówki są liczbami pierwszymi, jak nie to powiększasz różnicę miedzy połówkami nimi i znowu test Millera-Rabina i tak, aż do skutku.