Lexiq

Eratoszthenész szitája

Eratoszthenész szitája egy egyszerű módszer a prímszámok megtalálására.

Eratoszthenész szitájának grafikus ábrázolásaAz algoritmus a következőképp néz ki:

  1. Írd fel egymás után az egész számokat 2‑től addig, ameddig a prímtesztet csinálni szeretnéd!
  2. Az első át nem húzott szám lesz a következő prím. Írd fel a prímek közé, és húzd le listádról az összes többszörösével együtt!
  3. Ismételd a 2‑es pontot addig, amíg vannak át nem húzott számok a listádon.

Ha például 10‑ig érdekelnek a prímszámok, akkor első lépésben fel kell írni a számokat 2‑től 10‑ig:

2, 3, 4, 5, 6, 7, 8, 9, 10

A második lépésben a 2‑es számot fel kell írni a prímek közé, és az összes többszörösével együtt át kell húzni:

2, 3, 4, 5, 6, 7, 8, 9, 10

A következő prímszám tehát az első át nem húzott szám, azaz a 3‑as. A prímek között így most a 2 és a 3 van, és a 3‑as számot az összes többszörösével együtt át kell húzni:

2, 3, 4, 5, 6, 7, 8, 9, 10

A következő prímszám tehát az 5‑ös. A kiírt prímek között így most a 2, 3 és az 5 van, és a 5‑ös számot az összes többszörösével együtt át kell húzni (a mi esetünkben csak a 10 lenne a többszöröse, de az már át van húzva):

2, 3, 4, 5, 6, 7, 8, 9, 10

A következő prímszám tehát a 7‑es. A prímek listája 2, 3, 5, 7, és mivel a 7‑es szám áthúzásával nem marad több át nem húzott szám, készen is vagyunk.

A módszert megalkotójáról, az Eratoszthenész Pentatlosz ókori görög matematikusról nevezték el, a szita szó pedig arra utal, hogy a prímszámok úgy hullanak ki a módszer alkalmazása során, mintha egy szitán szűrnénk ki őket.