Eratoszthenész szitája

A prímszámok előállításának ma is használt módszere Eratoszthenész görög matematikustól származik. Az elnevezés utal az eljárás lényegére, mivel az 1-től n-ig felírt egész számok közül „kiszitáljuk” az összetett számokat. Amely számok fennmaradnak a „szitán” (az 1 kivételével) azok a prímek.

Az eljárás:

1. Írjuk fel a számokat 1-től n-ig, (itt például 100-ig) egyesével.
2. Keressük meg az első olyan 1-től nagyobbat, amelyik még nincs sem kihúzva, sem megjelölve. Elsőként ez a 2.
3. Ezután húzzuk ki ennek többszöröseit, de őt pedig jelöljük meg.
4. Ismételd meg a második lépéstől újra az eljárást. Természetesen egy összetett szám többször is kihúzásra kerülhet.
5. Az algoritmus akkor álljon le, ha a második lépésnél talált szám négyzete már nagyobb, mint n.