Programozó versenyek

Magas szintű programozási nyelvek 1, egyéni verseny, 2016. április 10.

2016. április 10. 10:00 – 2016. április 10. 15:00

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
Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.