Eratosthenovo síto

Ukážeme si postup používaný ve starém řecku pro generování posloupnosti prvočísel menších jak ,N' známý jako Eratosthenovo síto. Eratosthenes se narodil 276 let před naším letopočtem takže tento postup je přes 2200 let starý. Proto je velmi jednoduchý a elegantní takže ho zvládne úplně každý. Ukážeme na příkladu: Chceme spočítat všechna prvočísla až do 100. Funguje to úplně stejně i pro počítání prvočísel až do tisíce nebo milionu. Postup je následujcí: Na začátku máme všechna čísla neoznačená. Šedé políčko je neoznačené. Začneme od prvního čísla a jestli je neoznačené pak je prvočíslo. Takže narazíme na 2 vidíme, že 2 je prvočíslo, protože je neoznačené. Druhým krokem je že vyškrtneme všechny násobky 2 protože víme, že jsou složená takže -prásk- trochu poposkočíme a odstraníme všechny násobky 2 Červené znamená složené číslo Nyní opakujeme postup. Přejdeme ze 2 na 3 Číslo 3 je neoznačené, takže ho označíme jako prvočíslo Teď můžeme vyškrtnout všechny násobky 3 Existuje jednoduchý zlepšovák: Všimneme si, že číslo 6 je už označené je lepší označovat čísla až od druhé mocniny. 3 krát 3 je 9 Začneme tedy od 9 a vyškrtneme všechny násobky 3 jako složená čísla. Opět jdeme od prvního kroku a přejdeme na 4 Číslo 4 je označené, takže je složené přeskočíme na číslo 5 vidíme že je neoznačené, takže 5 je prvočíslo Vezmeme 5 krát 5 je 25 začneme od 25 a vyškrtneme 25, 30, 35, 40, 45 a tak dále. Všechna tato čísla jsou složená. Pokračujeme dokud nenarazíme na číslo 7 vidíme že 7 je prvočíslo, protože není označené. 7 krát 7 je 49 označíme tedy 49 a všechny vyšší násobky 7 jako složená čísla. Opět pokračujeme až narazíme na 11 číslo 11 je prvočíslo Všimneme si, že 11 krát 11 je větší jak 100, takže můžeme zastavit v tomto bodě. Mohli jsme zastavit už na čísle 10 protože všechna zbývající neoznačená čísla pokud jsme si všimli, jsou prvočísla a proto je můžeme jedním šmahem označit všechna jako prvočísla. A to je celý algoritmus. Je opravdu velmi jednoduchý. Zobecníme postup abychom ho mohli zapsat do programu který bude prosévat čísla a najde tak všechna prvočísla až do čísla ,N' Nejdříve napíšeme hlavní smyčku takže máme " pro všechna čísla ,a' " od 2 do odmocniny z ,N' všimneme si, že zastavíme u čísla 10 -- ukázal jsem to jako 11 -- kde doopravdy zastavíme protože jsme našli všechna prvočísla. Takže pro ,a' od 2 do odmocniny z ,N' budeme postupovat: pokud ,a' je neoznačené tak víme, že je prvočíslo a když najdeme prvočíslo označíme všechny násobky ,a' jako složená čísla a to je vše. Takže pokud najdeme prvočíslo vyškrtneme všechny jeho násobky vrátíme se na začátek, inkrementujeme ,a' o 1 takže jsme na čísle 2, poté pokračujeme na 3 poté jdeme na 4, 5 a tak dále A když jsme hotovi, máme všechna prvočísla. Všimneme si, že tohle je také smyčka takže máme hlavní ,for' smyčku a když najdeme prvočíslo tak vyškrtávání násobků je také smyčka takže je důležité si všimnout že zde máme vnořenou smyčku -- -- smyčku uvnitř smyčky. Tady je ukázka algoritmu v akci napsal jsem to v javascriptu níže pokud zadám 100 tak dostanu všechna prvočísla menší jak 100 a pokud zadám 200 dostanu všechna prvočísla pod 200 a pokud zadám 850 dostanu prvočísla menší než 850 A tady níže mám program se záznamem jak jsem to nastavil.