Eratosztenész szitája egy ókori algoritmus, amely arra szolgál, hogy az összes prímszámot megtaláljuk 2 és egy megadott N szám között.
Az algoritmus a következő lépésekből áll:

1. Egymásután felírjuk a számokat 2 és N között
2. Kezdve az első prímszámtól (2), minden többszörösét (4, 6, 8, 10, ...) kihúzzuk N ig, mivel azok nem prímek
3. Továbbmegyünk a következő nem kihúzott számig (3) és minden többszörösét (6, 9, 12, ... ) kihúzzuk, mivel azok nem prímek
4. Addig ismételjük a 3 as lépést, amíg el nem érünk N ig
5. Azokat a számokat, amelyek nem lettek kihúzva, kiírjuk

Egy vizuális ábrázolásért lásd:   wiki