Eratosthenovo síto je jednoduchý algoritmus pro nalezení všech prvočísel nižších, než je daná horní mez. Tento algorimus je připisován starořeckému učenci Eratosthenovi z Kyrény a je datován cca. do roku 200 př.n.l. Jedná se o jednu z nejefektivnějších metod pro hledání pročísel do . Pro prvočísla vyšší hodnoty je vhodné využít jiných testů (Rabin-Millerův test, Lehmannův test...).

Princip

Algoritmus se skládá z následujících kroků:

1. Napíšeme všechna čísla 2 až n (2 je první prvočíslo). A předpokládáme, že všechna jsou prvočísla.
2. Vezmeme si první prvočíslo a víme, že všechny jeho násobky nemohou být z definice prvočísly, proto je vyškrtneme z našeho seznamu.
3. Nyní si vezmeme další prvočíslo z proškrtaného seznamu a opět vyházíme všechny jeho násobky.
4. Opakujeme 3, dokud nedojdou čísla.

Zlepšení algoritmu: nemá smysl ověřovat všechna čísla, stačí do odmocniny horní meze, protože pokud by horní mez byla složeným číslem (ve tvaru ), tak nebo . Z tohoto důvodu, pokud nejvyšší testované číslo není prvočíslem, tak je prověřeno v nejhorším případě při čítání své odmocniny, všechny další testy jsou zbytečné.

Asymptotická složitost

Asymptotická složitost Eratosthenova síta je , kde je horní mez.

Příklad

Najděte prvočísla do 20.

Vypíšeme si všechna čísla 2-20.

Vyškrtáme násobky dvojky.

Vyškrtáme násobky trojky.

– jsme hotovi.

Kód

 
    /**
      * Eratosthenovo sito
      * @param upperBound horni mez, prvni cislo, ktere jiz 
      * nebude vyhodnoceno
      */
     public static void sieveOfEratosthenes(int upperBound){
         boolean[] sieve = new boolean[upperBound];
         //jsme v jave, inicializovano rovnou na false
         //true == je slozene
         //false == je prvocislo
         sieve[0] = sieve[1] = true; //nula a jedna nejsou prvocisla
         for(int i = 2; i <= Math.sqrt(sieve.length); i++){
             if(sieve[i] == true) continue;
             for(int j = 2*i; j < sieve.length; j += i){ //samotne citani
                 sieve[j] = true; //nemuze byt z definice prvocislem (je nasobkem jineho cisla)
             }
         }
         printSieve(sieve); //na zaver vypiseme prvocisla
     }
 
     /**
      * Vypise obsah sita
      * @param sieve sito true == je slozene, false == je prvocislo
      */
     private static void printSieve(boolean[] sieve) {
         System.out.println("Prvocisla do cisla " + sieve.length);
         for (int i = 2; i < sieve.length; i++) {
             if(sieve[i] == false) System.out.print(i + " ");      
         }
     }
 

  
 /**
  * Eratosthenovo sito
  * @param upperBound horni mez, prvni cislo, ktere jiz 
  * nebude vyhodnoceno
  */
 void sieveOfEratosthenes(int upperBound){
     bool * sieve = new bool[upperBound];
     for(int i = 0; i < upperBound; i ++){
         sieve[i] = false;
     }
     //true == je slozene
     //false == je prvocislo
     sieve[0] = sieve[1] = true; //nula a jedna nejsou prvocisla
     for(int i = 2; i <= sqrt((double)upperBound); i++){
         if(sieve[i] == true) continue;
         for(int j = 2*i; j < upperBound; j += i){ //samotne citani
             sieve[j] = true; //nemuze byt z definice prvocislem (je nasobkem jineho cisla)
         }
     }
     printSieve(sieve, upperBound); //na zaver vypiseme prvocisla
     delete[] sieve;
 }
 
 /**
  * Vypise obsah sita
  * @param sieve sito true == je slozene, false == je prvocislo
  * @param size velikost pole
  */
 void printSieve(bool * sieve, int size) {
     for (int i = 2; i < size; i++) {
         if(sieve[i] == false) cout << i << " ";     
     }
 }