Eratosthenovo síto je algoritmus pro výběr prvočísel z dané množiny. Tento algoritmus je poměrně snadný a lehce pochopitelný. Je pojmenován po řeckém matematikovi Eratosthenovi.
Tento algoritmus se nazývá sítem, protože se množina čísel takzvaně prosívá. Nejprve se všechny hodnoty nastaví na „true“, tedy jako prvočísla a následně se z nich odebírají složená čísla.
Jednoduchý příklad:
Dejme tomu, že chceme vypsat všechna prvočísla do čísla 10. Začneme samozřejmě logicky od čísla 2, protože číslo jedna není prvočíslem.
Nastavíme si tedy nejprve všechna od čísla 2 na prvočísla – označíme si je tučne (jako true).
2, 3, 4, 5, 6, 7, 8, 9, 10
Nyní vezmeme první prvočíslo (2) a nastavíme všechny jeho násobky, jako čísla složená (false).
2, 3, 4, 5, 6, 7, 8, 9, 10
V tuto chvíli uděláme to samé s dalším prvočíslem, které je v řadě (3).
2, 3, 4, 5, 6, 7, 8, 9, 10
Nyní bychom pokračovali dalším číslem, které je označeno jako prvočíslo, což by v tuto chvíli bylo číslo 5. To ale nemusíme, protože nám to již stačí a můžeme již jen vypsat výsledek.
2, 3, 5, 7
Pro lepší pochopení může posloužit tato demonstrativní animace.
A tady je zdrojový kod pro jazyk Java:
//vytvoříme proměnou
int max_cislo;
//vytvoření pole typu boolean s počtem prvků maximalního čísla
boolean[] pole = new boolean[max_cislo+1];Toto pole musíme naplnit hodnotami true. Tím všechny čísla nastavíme na prvočísla.
for(int i = 2;i < pole.length;i++) {
pole[i]=true;
}V tuto chvíli stačí napsat cykly, které budou procházet pole a nastavovat hodnoty false u složených čísel. Stačí, když budeme procházet první polovinu čícel. Na funcionalitě algoritmu to nic nemění, je to logicky správně a především to spoří výpočetní čas.
for(int i = 2;i*i < pole.length;i++) {
//kdyz je cislo na pozici true - prvočíslem
if(pole[i] == true) {
//spust cyklus, ktery nastavi vsechny nasobky cisla "i" na false
for(int j = 2;j*i < pole.length;j++) {
pole[j*i] = false;
}
}
}Po tomto kroku máme již připravené pole s prvočísly – stačí již provést výpis. Způsob výpisu si může nastavit jakkoliv chce. Já prvočísla pouze oddělil mezerou.
//cyklus ktery vypise prvocisla z naseho pole
for(int i = 2;i < pole.length;i++) {
if(pole[i] == true) {
System.out.print(i+" ");
}
}
Zde si ještě můžete stáhnout celou třídu s tímto algoritmem - erathostenovo_sito.java.
Další informace a implementace algoritmu do různých jazyků naleznete na wikipedii.
2008-11-14 15:19:23
Good job
2009-09-13 15:38:35
Jen mi neni jasne, proc se do pole "pole" uklada pocet prvku max +1. Muzete mi to vysvetlit?
2009-09-17 12:15:52
Ahoj, musíš přidat o prvek víc, protože musíč počítat taky s nulou, která ti zabere jednu pozici. Musíš koukat na to, že pozice v poli je číslovaná logicky od nuly. A v tomhle případě bereme, že x-tá pozice v poli je skutečné číslo x.
2009-09-29 23:28:12
Ahoj, sry, ze jsem poprve nepozdravil! Diky za vysvetleni, uz to chapu. Nak mi to hned nedoklaplo. :-D