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.

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ó bal oldalá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 nincs minden szám áthúzva.

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

Programkód C++-ban

Optimális C++ kód, fájlba írással

//Az első M (itt 50) szám közül válogassuk ki a prímeket, fájlba írja az eredményt - Eratoszthenész Szitája
#include <iostream>
#include <fstream>
 
using namespace std; 
int main()
{
    ofstream fout;
    string nev; 
    cout << "Nev: "; cin >> nev; //fájlnév bekérése
    fout.open(nev.c_str());      //fájl létrehozása
 
    const int M=50; //Meddig vizsgáljuk a számokat
    fout <<"A(z) " << M << "-nel nem nagyobb primszamok:\n"; //A fájl bevezető szövege
    bool tomb [M+1]; //logikai tömböt hozunk létre
    tomb[0]=tomb[1]=false; // a 0-át és az 1-et alapból hamisnak vesszük, hiszen nem prímek.
                          for (int i=2;i<=M;++i) tomb[i]=true; //2-től indítjuk a for-t, alapból mindent igazra állítunk.
                              int j=2; //indexet ezzel figyelem
                              while (j<=M) {
                                    for(int i=j*j; i<=M; i+=j) tomb [i] = false;// a többszörösök logikai értékét hamisra állítom
                                    while(tomb[++j]==false);}  // ha a következő érték hamis, akkor továbbugrik a következőre
 
                                  for(int i=0;i<=M;++i)
                                      if(tomb[i]) //megnézzük hogy igaz-e
                                        fout<<i<<" "; // kiírja a fájlba a számokat, szóközzel elválasztva
}

Programkód Pascal-ban

var n,i,j,p:longint;
    a:array[1..2000000] of boolean; //logikai tömböt hozunk létre
    fout:text; //kimeneti fájl
Begin
 assign(fout,'Név'); rewrite(fout); 
 n:=2000000; //az n lehet bármilyem érték ami belefér longint-ba
 a[1]:=false; //az a[1] 0-t vesz fel mivel az 1 nem primszám
  for i:=2 to n do a[i]:=true; //feltöltjuk a tömbök 1-esekkel 
  p:=2;
   while p*p <= n do begin
     j:=p*p;
        while (j<= n) do begin
         a[j]:=false; //a többszörösöket hamissá váltjuk
           j:=j+p;
             end;
         repeat p:=p+1 until a[p]=true; //ha a következő érték hamis, akkor továbbugrik 
             end; 
 for i:=1 to n do if a[i]=true then write(fout,i,' '); //kiiratjuk azokat az elemeket amelyek igazak maradtak,vagyis primszámok
close(fout);
End.

Programkód Python-ban.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
lst = [1]*1000                      # létrehozunk egy listát, ebben a példában (1000) elemmel
for i in range(2,1000):             # A lista bejárása a 2 indexértéktől kezdve  
    for j in range(i*2, 1000, i):   # a listának azon elemeihez, melyek indexe az i-nek többszörösei, nullás (false) értéket rendelünk
        lst[j] = 0
for i in range(2,1000):             # Kiíratjuk azoknak az elemeknek az indexét, melyek értéke 1 maradt
    if lst[i]:
        print i,

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.

További információk

• Animált eratoszthenészi szita 1000-ig
• Java Script animáció