Eratosthenovo síto

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.

Příklad 
Pro nalezení prvočísel mezi prvními 30 čísly:

Krok 1: Seznam obsahuje všechna čísla v rozsahu 2–30:
 Seznam: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 {| class="wikitable" style="text-align: center"
|-
|   || 2 || 3 || 4 || 5
|-
| 6 || 7 || 8 || 9 || 10
|-
| 11 || 12 || 13 || 14 || 15
|-
| 16 || 17 || 18 || 19 || 20
|-
| 21 || 22 || 23 || 24 || 25
|-
| 26 || 27 || 28 || 29 || 30
|}

Krok 2: Odebereme první číslo ze seznamu (2) 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 21 22 23 24 25 26 27 28 29 30
 {| class="wikitable" style="text-align: center"
|-
|  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 2
| 3
| 4
| 5
|-
| 6 || 7 || 8 || 9 || 10
|-
| 11 || 12 || 13 || 14 || 15
|-
| 16 || 17 || 18 || 19 || 20
|-
| 21 || 22 || 23 || 24 || 25
|-
| 26 || 27 || 28 || 29 || 30
|}

Krok 3: Odebereme ze seznamu všechny násobky právě odebraného prvočísla (4, 6, 8, 10, …):
 Známá prvočísla: 2
 Seznam: 3 5 7 9 11 13 15 17 19 21 23 25 27 29
 {| class="wikitable" style="text-align: center"
|-
|  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 2
| 3
|  
| 5
|-
|   || 7 ||   || 9 ||  
|-
| 11 ||   || 13 ||   || 15
|-
|   || 17 ||   || 19 ||  
|-
| 21 ||   || 23 ||   || 25
|-
|   || 27 ||   || 29 ||  
|}

Krok 4: Pokračujeme opět krokem 2, dokud zbývají nějaká čísla (první číslo v seznamu a také prvočíslo je tentokrát 3):
 Známá prvočísla: 2 3
 Seznam: 5 7 9 11 13 15 17 19 21 23 25 27 29
 {| class="wikitable" style="text-align: center"
|-
|  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 2
| style="border: 3px solid darkgrey; background:#e1e1e1" | 3
|  
| 5
|-
|   || 7 ||   || 9 ||  
|-
| 11 ||   || 13 ||   || 15
|-
|   || 17 ||   || 19 ||  
|-
| 21 ||   || 23 ||   || 25
|-
|   || 27 ||   || 29 ||  
|}

Krok 5: Nyní zopakujeme krok 3, avšak pro právě odebrané číslo (3):
 Známá prvočísla: 2 3
 Seznam: 5 7 11 13 17 19 23 25 29
 {| class="wikitable" style="text-align: center"
|-
|  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 2
| style="border: 3px solid darkgrey; background:#e1e1e1" | 3
|  
| 5
|-
|   || 7 ||   ||   ||  
|-
| 11 ||   || 13 ||   ||  
|-
|   || 17 ||   || 19 ||  
|-
|   ||   || 23 ||   || 25
|-
|   ||   ||   || 29 ||  
|}

Krok 6 a 7: Po dalším opakování pro číslo 5 a po odebrání jeho násobků:
 Známá prvočísla: 2 3 5
 Seznam: 7 11 13 17 19 23 29
 {| style="text-align: center; border-collapse: collapse;"
|- style="height: 30px" |
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 3px solid darkgrey; width: 24px; background:#e1e1e1" | 2
| style="border: 3px solid darkgrey; width: 24px; background:#e1e1e1" | 3
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 3px solid darkgrey; width: 24px; background:#e1e1e1" | 5
|  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 3px solid darkgrey; width: 24px; background:#e1e1e1" | 2
| style="border: 3px solid darkgrey; width: 24px; background:#e1e1e1" | 3
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 3px solid darkgrey; width: 24px; background:#e1e1e1" | 5
|- style="height: 30px" |
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 7
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
|  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 7
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
|- style="height: 30px" |
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 11
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 13
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
|  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 11
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 13
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
|- style="height: 30px" |
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 17
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 19
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
|  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 17
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 19
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
|- style="height: 30px" |
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 23
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 25
|  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 23
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
|- style="height: 30px" |
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 29
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
|  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" | 29
| style="border: 1px solid darkgrey; width: 24px; background:#f8f8f8" |  
|}

Následující prvočíslo 7 je vyšší než √29, takže zbývají už jen prvočísla. (Kdyby ještě existovalo v seznamu číslo X, které je součinem dvou celých čísel A·B, musel by např. činitel A být menší než (nebo roven) √X a druhý činitel B pak větší než (nebo roven) √X. Všechny násobky celých čísel menších než √30 jsou již ale ze seznamu odebrány, včetně X. Tím pádem se již v seznamu nenachází žádné číslo, které lze rozložit na součin.)

Výsledný seznam prvočísel v rozsahu 2–30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
 {| class="wikitable" style="text-align: center"
|-
|  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 2
| style="border: 3px solid darkgrey; background:#e1e1e1" | 3
|  
| style="border: 3px solid darkgrey; width: 17px; background:#e1e1e1" | 5
|-
|  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 7
|   ||   ||  
|-
| style="border: 3px solid darkgrey; background:#e1e1e1" | 11
|  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 13
|   ||  
|-
|  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 17
|  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 19
|  
|-
|   ||  
|style="border: 3px solid darkgrey; background:#e1e1e1" | 23
|   ||  
|-
|   ||   ||  
| style="border: 3px solid darkgrey; background:#e1e1e1" | 29
|  
|}

Příklad implementace 
Následující kód je v jazyce Python.

def eratosthenovo_sito(do):
  do += 1
  sito = [True] * do
 
  for i in range(2, do):
    if sito[i]:
      for j in range(i**2, do, i):
        sito[j]=False
 
  prvocisla=[]
  for i in range(2, do):
    if sito[i]:
      prvocisla.append(i)
  return prvocisla

Následující kód je v jazyce PHP.
function eratosthenovo_sito($max) {
  for ($i=2; $i<=$max; $i++) {
    $cisla[$i]=true;
  }
  foreach ($cisla as $key => $val) {
    for ($i=$key*$key; $i <= $max; $i+=$key) { 
      if (isset($cisla[$i])) {
        unset($cisla[$i]);
      }
    }
  }
  return $cisla;
}

Externí odkazy 
 
 Interaktivní animace  (vyžadován JavaScript)

Testy prvočíselnosti