Algoritmizácia a programovanie - Slovne popísané algoritmy - Eratostenovo sito :)

Metóda hľadania prvočísel, ktoré sú deliteľné len samým sebou a jednotkou[1]. Jej princípom je filtrovanie neprvočísel zo zoznamu všetkých čísel od 2 až po ľubovoľnú hornú hranicu.

Napríklad ak chceme nájsť všetky prvočísla do 50:

1. Vypíšeme všetky čísla od 2 do 50.
2. Zakrúžkujeme 2 a vyčiarneme všetky násobky 2 (4, 6, 8...).
3. Zakrúžkujeme ďalšie číslo, ktoré nie je vyčiarknuté a preškrtneme všetky násobky toho čísla.
4. Opakujeme krok 3, až dokiaľ nedosiahneme koniec zoznamu. Prvočísla sú tie, ktoré sú zakrúžkované.

Výsledok aplikovania uvedeného postupu

[1] Ktorá podľa dohody nie je prvočíslom.

Hodnotenie užitočnosti článku:

• ← Algoritmizácia a programovanie - Slovne popísané algoritmy - Delové gule a pyramídy :)
• Algoritmizácia a programovanie - Slovne popísané algoritmy - Hanojské veže :) →