A Goldbach-sejtés

1742-ben Christian Goldbach, egy német amatőr matematikus, levelet küldött Leonhard Eulernek, amelyben az alábbi sejtést írta le:

Minden 2-nél nagyobb természetes szám felírható három prímszám összegeként.

Goldbach az 1-et prímszámnak tekintette; ezt a konvenciót már nem követjük. Euler később átfogalmazta a sejtést a következőképpen:

Minden 4-nél nagyobb vagy egyenlő páros szám kifejezhető két prímszám összegeként.

Például:

• 8 = 3 + 5. A 3 és az 5 is páratlan prímszámok.
• 20 = 3 + 17 = 7 + 13.
• 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

Még ma sincs bebizonyítva, hogy a sejtés vajon igaz-e. (Várjunk csak: nekem persze megvan a bizonyítás, csak túl hosszú ahhoz, hogy ide írjam az oldal margójára.)

Mindenesetre most az a feladatod, hogy ellenőrizd Goldbach sejtését, ahogy Euler megfogalmazta, az egymilliónál kisebb páros számokra.

A bemenet specifikációja

A bemenet egy vagy több tesztesetet tartalmaz. Minden teszteset egyetlen páros egész számból, n-ből áll, ahol 6 ≤ n < 1 000 000. A bemenetet egy 0 értékű n zárja.

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni n = a + b formában, ahol a és b páratlan prímek. A számokat és az operátorokat pontosan egy szóközzel kell elválasztani egymástól, ahogy a példa kimeneten látható. Ha több olyan páratlan prímekből álló számpár is létezik, amelyek összege n, akkor azt a számpárt válaszd, amelyre a b – a különbség maximális.

Ha nincs ilyen számpár, akkor a „Goldbach's conjecture is wrong.” sort kell kiírni.

Példa bemenet

1. 8
2. 20
3. 42
4. 0

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 8 = 3 + 5
2. 20 = 3 + 17
3. 42 = 5 + 37

letöltés szöveges állományként