Eratosfénové mřížky: způsoby, jak najít prvočísla

V matematice existují různé metody pro nalezení prvočísel, z nichž jednou je metoda známá jako "Eratosfénové mřížky". Jedná se o algoritmus, který umožňuje najít všechna prvočísla před daným číslem.

Metoda je založena na principu vyloučení: nejprve se vytvoří seznam všech čísel od 2 do daného čísla, poté jsou ze seznamu vyloučena čísla násobky 2, Poté čísla násobky 3 a tak dále. Čísla, která zůstanou v seznamu Po dokončení procesu, budou jednoduchá čísla.

Tato metoda byla pojmenována po starověkém řeckém matematikovi Eratosthenu Kirenském, který žil ve 3.století př. n. l. jako první navrhl tento algoritmus ve své práci o teorii čísel.

Eratosthen

Princip fungování eratosférické mřížky je založen na důsledném vyškrtnutí všech násobků čísel, počínaje dvojkou. Poté všechna nevyčíslitelná čísla zůstanou jednoduchá.

Algoritmus eratosfénové mřížky lze představit jako tabulku. Nejprve je nutné vytvořit tabulku s čísly od 2 do n, kde n je horní hranice rozsahu. Poté je třeba vyškrtnout čísla začínající na 2, a to tak, že každé číslo vynásobíme čísly, která jsou pro něj násobky. Poté je nutné proces opakovat pro další nezaškrtnuté číslo a opakovat jej, dokud nebudou zkontrolována všechna čísla z rozsahu.

Po dokončení algoritmu zůstanou všechna nevyčíslitelná čísla jednoduchá a lze předpokládat, že jsme dostali všechna prvočísla v daném rozsahu.

Eratosthenova mřížka je tedy účinný algoritmus pro nalezení prvočísel založených na jejich stručnosti.

Definice algoritmu

1. Vytvoří se seznam všech čísel od 2 do zadaného čísla N.

2. Počínaje číslem 2 je označen jako prvočíslo a všechna jeho násobky jsou vyškrtnuty ze seznamu.

3. Přejdeme k dalšímu neoznačenému číslu a opakujeme Krok 2.

4. Opakujeme kroky 2 a 3, dokud neprojdeme všemi čísly v seznamu.

Na konci algoritmu jsou všechna zbývající čísla v seznamu prvočísla.

Pro pohodlí se použije zobrazení tabulkou, kde sloupce označují čísla a řádky kroky algoritmu. Každá buňka tabulky udává, zda je číslo označeno jako prvočíslo nebo vyškrtnuto ze seznamu.

Kde " P "znamená, že číslo je označeno jako prvočíslo a" N " znamená, že číslo je vyškrtnuto ze seznamu.

Eratosfénové mřížky jsou účinným způsobem, jak najít prvočísla, protože nevyžadují kontrolu každého čísla na dělitelnost, ale pouze vyškrtávají složená čísla ze seznamu.

Kroky algoritmu

Algoritmus Eratosfénové mřížky je založen na myšlence najít všechna prvočísla před daným číslem N. níže jsou uvedeny hlavní kroky daného algoritmu:

• Vytvořte seznam čísel od 2 do N.
• Nastavte počáteční hodnotu proměnné p na 2.
• Označte všechna čísla násobky p jako složená.
• Najděte první neoznačené číslo v seznamu, které následuje po p, a nastavte jeho hodnotu na p.
• Opakujte kroky 3-4 pro všechna neoznačená čísla na N.
• Všechna neoznačená čísla v seznamu jsou prvočísla.

Algoritmus Eratosfénové mřížky umožňuje efektivně vyhledávat prvočísla na danou hodnotu N. Je založen na principu vyloučení složených čísel a umožňuje snížit počet kontrol při hledání prvočísel.

Příklad použití

Pro názorný příklad použití Eratosférické mřížky si představíme tabulku o rozměrech 10x10, ve které chceme najít všechna prvočísla.

Použijeme - li algoritmus Eratosfénové mřížky, vyškrtneme všechna čísla, která se dělí prvočísly na kořen z největšího čísla, v tomto případě na 10. Zůstanou jen prvočísla: 2, 3, 5, 7.