Eratosthenovo síto
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ů:
- Napíšeme všechna čísla 2 až n (2 je první prvočíslo). A předpokládáme, že všechna jsou prvočísla.
- 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.
- Nyní si vezmeme další prvočíslo z proškrtaného seznamu a opět vyházíme všechny jeho násobky.
- 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 << " ";
}
}
