Bevezetés
Egy garázsvásárláson vettél egy nagy doboz vegyes számítógép-alkatrészt.
Elkezdted összerakni az alkatrészeket, hogy egyedi számítógépeket építs belőlük.
Szeretnéd tesztelni, hogyan teljesítenek a különböző alkatrészkombinációk, ezért úgy döntesz, hogy írsz egy saját benchmarkprogramot, amivel összehasonlíthatod a gépeidet.
A híres „Eratoszthenész szitája” algoritmust választod: ősi algoritmus, de olyan, amely alaposan próbára teszi a gépeidet.
Utasítások
A feladatod, hogy készíts egy programot, amely megvalósítja az Eratoszthenész szitája algoritmust, és megkeresi az adott számnál nem nagyobb összes prímszámot.
A prímszám olyan 1-nél nagyobb szám, amely csak 1-gyel és önmagával osztható.
Például a 2, 3, 5, 7, 11 és 13 prímszámok.
Ezzel szemben a 6 nem prímszám, mert nemcsak 1-gyel és önmagával, hanem 2-vel és 3-mal is osztható.
Az Eratoszthenész szitájának használatához először írd fel az összes számot 2-től egészen az adott számig, azt is beleértve.
Ezután kövesd az alábbi lépéseket:
- Keresd meg a következő meg nem jelölt számot (a megjelölteket kihagyva).
Ez egy prímszám.
- Jelöld meg a prímszám összes többszörösét nem prímként.
Ismételd a lépéseket, amíg az összes számon végig nem mentél.
A végén az összes meg nem jelölt szám prímszám.
Az Eratoszthenész szitája összeadással (a prímszám ismételt hozzáadásával) vagy szorzással (a többszöröseinek közvetlen kiszámításával) jelöli meg az egyes prímszámok többszöröseit, ahelyett hogy minden számnál ellenőrizné az oszthatóságot.
A tesztek nem azt ellenőrzik, hogy megvalósítottad-e az algoritmust, csak azt, hogy a helyes prímszámokat adtad-e meg.
Példa
Tegyük fel, hogy a 10-nél nem nagyobb prímszámokat keresed.
-
Írd fel a 2, 3, 4, 5, 6, 7, 8, 9, 10 számokat úgy, hogy egyik sincs megjelölve.
2 3 4 5 6 7 8 9 10
-
A 2 nincs megjelölve, ezért prímszám.
Jelöld meg a 4-et, 6-ot, 8-at és 10-et „nem prímként”.
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
A 3 nincs megjelölve, ezért prímszám.
Jelöld meg a 6-ot és a 9-et nem prímként (a 6 megjelölése nem kötelező, mert már meg van jelölve).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
A 4 „nem prímként” van megjelölve, ezért kihagyjuk.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
Az 5 nincs megjelölve, ezért prímszám.
Jelöld meg a 10-et nem prímként (nem kötelező, mert már meg van jelölve).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
A 6 „nem prímként” van megjelölve, ezért kihagyjuk.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
A 7 nincs megjelölve, ezért prímszám.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
A 8 „nem prímként” van megjelölve, ezért kihagyjuk.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
A 9 „nem prímként” van megjelölve, ezért kihagyjuk.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
A 10 „nem prímként” van megjelölve, ezért megállunk, mert nincs több ellenőrizendő szám.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Végignézted az összes számot, és azt találtad, hogy a 2, 3, 5 és 7 továbbra sincs megjelölve, ami azt jelenti, hogy ezek a 10-nél nem nagyobb prímszámok.
