Eratosthenovo síto

Z Wikipedie, otevřené encyklopedie

Eratosthenovo síto je jednoduchý algoritmus pro nalezení všech prvočísel menších než zadaná horní mez. Je pojmenován po řeckém matematikovi Eratosthenovi z Kyrény, který žil v letech 276–194 př. n. l.

Algoritmus funguje „prosíváním“ seznamu čísel – na počátku seznam obsahuje všechna čísla v daném rozsahu (2, 3, 4, …, zadané maximum). Poté se opakovaně první číslo ze seznamu vyjme, toto číslo je prvočíslem; ze seznamu se pak odstraní všechny násobky tohoto čísla (což jsou čísla složená). Tak se pokračuje do doby, než je ze seznamu odstraněno poslední číslo (nebo ve chvíli, kdy je jako prvočíslo označeno číslo vyšší než odmocnina nejvyššího čísla – v takové chvíli už všechna zbývající čísla jsou nutně prvočísly). Časová složitost tohoto algoritmu je O(N*log(log N)), kde N je horní mez rozsahu.

[editovat] Příklad

Pro nalezení prvočísel mezi prvními 20 čísly:

Krok 1: Seznam obsahuje všechna čísla v rozsahu 2–20:

Seznam: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Krok 2: Odebereme první číslo ze seznamu a označíme ho jako prvočíslo:

Známá prvočísla: 2

Seznam: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Krok 3: Odebereme ze seznamu všechny násobky právě odebraného prvočísla:

Známá prvočísla: 2

Seznam: 3 5 7 9 11 13 15 17 19

Krok 4: Pokračujeme opět bodem 2, dokud zbývají nějaká čísla

Známá prvočísla: 2 3

Seznam: 5 7 11 13 17 19

Známá prvočísla: 2 3 5

Seznam: 7 11 13 17 19

5 je vyšší než √19, takže zbývají už jen prvočísla.

Výsledný seznam prvočísel v rozsahu 2–20: 2, 3, 5, 7, 11, 13, 17, 19.

[editovat] Zdrojový kód v jazyce Pascal

program Ersíto
uses crt;
var Pole: array [2 .. MaxN] of boolean;
   i,j :integer;
begin
  for i := 2 to MaxN do 
    Pole[i] := true; {inicializace - predpokladame ze vsechna cisla jsou prvocisla, postupne budeme vyrazovat}
  i:=1;
  repeat
    i:=i+1;
    while (pole[i]=false) and (i<max) do i:=i+1; {najdeme cislo, u kterého je true}
    j:=i-1;  {optimalizace, aby jsme zbytečně nehledali násobky, které jsou již označené jako false z předchozího vyhledávání}
    while j*i<max do
       begin j:=j+1;
             pole[j*i]:=false; {najdeme všechny násobky daného prvočísla, které tudíž nejsou prvočísla}
       end;
  until i>sqrt(MaxN); {optimalizace, vysvětlena výše}
end;

[editovat] Zdrojový kód v jazyce Java

Výše uvedený kód v jazyce Pascal mi nefungoval, ale napsal jsem ho v Javě.

       int MaxN = 1024;        
       boolean[] Pole = new boolean[MaxN+1];
       int i,j;
       for (i=2;i<MaxN;i++) { /* Inicializace pole (vse jsou prvocisla a postupne budem vyrazovat) */
           Pole[i] = true; 
           }
       i=2;
       while (i*i <= MaxN) { /* dokud mocnina prvniho cisla na seznamu je mensi nez nejvetsi */
         if (Pole[i]){          /* pokud je i stale na seznamu (nezkoumej nasobky 4, kdyz jsme uz vyhodili nasobky 2 */
           j=2;                 /* j bude novy nasobek */
           while (i*j <= MaxN) {
               Pole[j*i] = false; /* cislo slozene */
               j++;
               }         
           } 
           i++;
       }

[editovat] Zdrojový kód v jazyce C++

 set<int> sito, prvocisla;
 int dalsi, nasobek;
 for (int i=2; i<=max; i++) sito.insert(i);
 dalsi = 2;
 do
 {
   while (sito.count(dalsi) == 0)
     dalsi++;
   prvocisla.insert(dalsi);
   nasobek = dalsi;
   while (nasobek <= max)
   {
     sito.erase(nasobek);
     nasobek += dalsi;
   }
 } while (!sito.empty());