Eratoszthenész szitája

A Wikipédiából, a szabad lexikonból.

Eratoszthenész szitája

Eratoszthenész szitája a neves ókori görög matematikus, Eratoszthenész módszere, melynek segítségével egyszerű kizárásos algoritmussal megállapíthatjuk, hogy melyek a prímszámok – papíron például a legkönnyebben 1 és 100 között.

Tartalomjegyzék

[szerkesztés] Az algoritmus

1. Írjuk fel a számokat egymás alá 2-től ameddig a prímtesztet elvégezni kívánjuk. Ez lesz az A lista. (Az animáció baloldalán.)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2. Kezdjünk egy B listát 2-vel, az első prím számmal. (Az animáció jobb oldalán.)
3. Húzzuk le 2-t és az összes többszörösét az A listáról.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4. Az első át nem húzott szám az A listán a következő prím. Írjuk fel a B listára.
5. Húzzuk át az így megtalált következő prímet és az összes többszörösét.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
6. Ismételjük a 3–5. lépéseket, amíg az A listán nem marad egyetlen át nem húzott szám se.

[szerkesztés] A pszeudokód

Az algoritmus pszeudokódja:

// legfeljebb ekkora számig megyünk el
utolso ← 100                   

// abból indulunk ki, hogy minden szám prímszám
ez_prim(i) ← igaz, i ∈ [2, utolso] 

for n in [2, √utolso]:
    if ez_prim(n):
        // minden prím többszörösét kihagyjuk,
        // a négyzetétől kezdve
        ez_prim(i) ← hamis, i ∈ {n², n²+n, n²+2n, ..., utolso}

for n in [2, utolso]:
    if ez_prim(n): nyomtat n

[szerkesztés] Források

Κόσκινον Ἐρατοσθένους or The Sieve of Eratosthenes (Being an Account of His Method of Finding All the Prime Numbers), Rev. Samuel Horsley, F. R. S. = Philosophical Transactions (1683–1775), 62(1772), 327–347.

[szerkesztés] Külső hivatkozások