Eratoszthenész szitája egy ősi, mégis rendkívül hatékony algoritmus a prímszámok meghatározására. Az i.e. 3. században Eratoszthenész, egy görög matematikus találta ki. Az algoritmus lényege, hogy egy adott határig kizárja a nem prímszámokat a prímszámok egyre szűkülő listájáról, mint egy szita segítségével. A módszer alapötlete, hogy az első prímszámoktól indulva (2-től), azok többszöröseit kihúzzuk, hiszen ezek nem lehetnek prímek. Ez a folyamat addig folytatódik, amíg el nem érjük a megadott határt. Az eredmény egy lista, amely csak és kizárólag prímszámokat tartalmaz.
Példák az Eratoszthenész szitájára:
-
10-ig található prímszámok meghatározása:
- Kezdjük a 2-vel (az első prím), és húzzuk ki a 4-et, 6-ot, 8-at, és 10-et.
- Folytassuk a 3-mal, és húzzuk ki a 6-ot és 9-et (bár a 6 már korábban ki lett húzva).
- Az eredmény: 2, 3, 5, 7.
-
20-ig található prímszámok meghatározása:
- Induljunk újra a 2-vel, és húzzuk ki a 4, 6, 8, 10, 12, 14, 16, 18, 20 számokat.
- Folytassuk a 3-mal, és húzzuk ki a 9, 12, 15, 18 (ismétlődések lehetnek).
- Folytassuk az 5-tel, és húzzuk ki a 10, 15, 20-at.
- Az eredmény: 2, 3, 5, 7, 11, 13, 17, 19.
Az Eratoszthenész szitája ma is alapszintű megismerés mindenki számára, aki érdeklődik a matematika és különösen a számelmélet iránt.
Vissza az előző oldalra