Eratoszthenész szitája
Eratoszthenész szitája egy ősi görög matematikus, Eratoszthenész Pentatlosz által kifejlesztett egyszerű és hatékony algoritmus, amelyet a prímszámok meghatározására használnak.
Az algoritmus a következőképpen működik melyet mi magunk is elkészíthetünk:
1. Készíts egy listát a 2-től n-ig terjedő összes egész számról.
2. Kezdd a legkisebb számmal (2). Ez a szám prímszám.
3. Távolítsd el a lista összes olyan többszörösét, amely nagyobb, mint az aktuális szám (kivéve magát a számot).
4. Lépj a következő számra a listában, amely még nincs áthúzva. Ez lesz a következő prímszám.
5. Ismételd meg a 3. és 4. lépéseket, amíg a lista végére nem érsz.
Az algoritmus végén a listában maradó számok mind prímek.
Példa az algoritmusra n = 30 esetén:
1. Kezdő lista: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
2. 2 prímszám, töröld a többszöröseit: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
3. Tovább 3-ra, töröld a többszöröseit: [2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
4. Tovább 5-re, töröld a többszöröseit: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
5. És így tovább…
A végén megmaradnak a prímszámok: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Ez az algoritmus különösen hasznos nagyobb számok esetében, mert hatékonyan képes kiszűrni a prímszámokat anélkül, hogy minden egyes számot külön-külön kellene ellenőrizni.