Eratosthenovo síto

Eratosthenovo síto: Kroky algoritmu pro prvočísla do 121. 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á). +more 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 :

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 :

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 :

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 :

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 :

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 :

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ř. +more č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. :

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 $val) { for ($i=$key*$key; $i

Externí odkazy

[url=http://www.faust.fr.bw.schule.de/mhb/eratosiv.htm]Interaktivní animace[/url] (vyžadován JavaScript)

Kategorie:Testy prvočíselnosti