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 írj egy programot, amely megvalósítja az Eratoszthenész szitája algoritmust, és megkeresi az összes prímszámot, amely kisebb vagy egyenlő egy adott számmal.
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 osztható, hanem 2-vel és 3-mal is.
Az Eratoszthenész szitája használatához először készíts egy listát az összes számról 2 és a megadott számod között.
Ezután ismételd meg a következő lépéseket:
- Keresd meg a listád következő meg nem jelölt számát (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.
Ezeket a lépéseket addig ismétled, amíg végig nem mentél a listád minden számán.
A végén az összes meg nem jelölt szám prím.
A tesztek nem ellenőrzik, hogy megvalósítottad-e az algoritmust, csak azt, hogy a prímek helyes listáját állítottad-e elő.
Annak ellenőrzésére, hogy helyesen valósítod-e meg a szitát, jó első teszt, ha megnézed, hogy nem használsz osztást vagy maradékképzést.
Példa
Tegyük fel, hogy a 10-nél kisebb vagy azzal egyenlő prímeket keresed.
- Sorold fel a 2, 3, 4, 5, 6, 7, 8, 9, 10 számokat, és hagyd őket jelöletlenül.
- A 2 jelöletlen, tehát prím.
Jelöld meg a 4-et, 6-ot, 8-at és 10-et „nem prím”-ként.
- A 3 jelöletlen, tehát prím.
Jelöld meg a 6-ot és a 9-et „nem prím”-ként (a 6 megjelölése opcionális, mert már meg van jelölve).
- A 4 „nem prím”-ként van megjelölve, ezért kihagyjuk.
- Az 5 jelöletlen, tehát prím.
Jelöld meg a 10-et „nem prím”-ként (opcionális, mert már meg van jelölve).
- A 6 „nem prím”-ként van megjelölve, ezért kihagyjuk.
- A 7 jelöletlen, tehát prím.
- A 8 „nem prím”-ként van megjelölve, ezért kihagyjuk.
- A 9 „nem prím”-ként van megjelölve, ezért kihagyjuk.
- A 10 „nem prím”-ként van megjelölve, ezért megállunk, mert nincs több ellenőrizendő szám.
Megvizsgáltad az összes számot, és azt találtad, hogy a 2, 3, 5 és 7 még mindig jelöletlen, ami azt jelenti, hogy ezek a 10-nél kisebb vagy azzal egyenlő prímek.
Megjegyzés
Hogy olvasható legyen a megoldásod, próbáld meg a refaktoráló eszközökkel kiemelni a jelentős részműveleteket, és ne törődj azzal, hogy jól elnevezett ideiglenes változókat használsz.
