AlgorithmO #11 — Решето на Ератостен
(Първо публикувано на 12.01.2017)
При днешния алгоритъм е по-интересна имплементацията, отколкото приложението му на ръка. Това е един класически числов алгоритъм за намиране на прости числа в интервал и определено си струва да го добавите към “арсенала” си. 😉
Очевидно е, че брадата прави играта… 🙂
ОПИСАНИЕ:
“Решетото на Ератостен” (да, решетоТО, а не просто решето :)) се използва за намирането на прости числа (т.е, числа, които се делят само на 1 и на себе си) в даден интервал. Името идва от думата “решето” — съд с дъно на дупки, през които отстраняваме ненужното (правили сте си спагети, нали?).
По същия начин, с този алгоритъм премахваме числата, които не отговарят на условието да са прости и след това филтриране получаваме резултата, който ни интересува.
Този алгоритъм е подходящ за малки числа (тъй като за големи става трудно приложим).
АЛГОРИТЪМ:
-
Записваме числата от 2 do ’n’ в редица.
-
Намираме първото нездраскано и немаркирано число в редицата.
Маркираме го като просто число. Да кажем, че това е числото ‘i’.
Задраскваме всяко i-то число след ‘i’ (т.е. задраскваме числата i+i, i+i+i и т.н. до края на интервала) -
Повтаряме стъпка 2 докато не остане нито едно незадраскано или немаркирано число. Маркираните са простите числа, които ни интересуват.
ПРИМЕР:
Нека намерим всички прости числа от 2 до 30 (n = 30).
Първо записваме всичките тези числа в редица (между другото, 1 го пропускаме, защото по дефиниция не се счита за просто):
Тъй като 2 е първото незадраскано и немаркирано число в редицата, маркираме го като просто (ще го “маркираме” като просто като го оцветим в червен цвят). След това задраскваме всеки 2-ри елемент след него:
Тъй като все още имаме незадраскани/нермаркирани елементи, отново трябва да намерим първият незадраскан и немаркиран елемент. Сега това е 3. Задраскваме всички елементи след него, които са кратни на 3:
Продължаваме по същата процедура. 4 е задраскан елемент, така че не ни върши работа, но 5 може да бъде маркиран. Задраскваме всеки 5-ти елемент след него:
Следващият елемент, който ще маркираме, е 7, тъй като преди него всички са маркирани или задраскани. Задраскваме всеки 7-ми елемент след него:
Е, всъщност не ни се наложи да задраскваме нищо ново… Продължаваме със следващия елемент, който отговаря на горното условие — 11. И за него се оказва, че ще е същото нещо и няма какво да задраскваме. Същото важи за елементите за 13, 17, 19, 23 и 29. Оказва се, че всички те са прости и просто ги маркираме като такива:
Стигнаме края — всички числа са или маркирани, или задраскани. Интересуват ни маркираните (оцветените в червено) — те са простите числа, в интервала от 2 до 30.
В случая, това са числата: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29.
Ако не вярвате — the proof is in the pudding. 😀
ИМПЛЕМЕНТАЦИЯ (Java):
(базирано на C имплементацията от книгата “Програмиране = ++Алгоритми” на Преслав Наков и Панайот Добриков — “Библията на състезанията по информатика” ;))
1) Инициализираме масив sieve[] с нули. По-късно, когато задраскаме някое число, на съот-ветната позиция в масива ще записваме 1. Въвеждаме променлива-брояч i, която показва кое число разглеждаме в момента (т.е. ще сочи първото незадраскано или немаркирано число). Инициализираме i = 2.
2) Увеличаваме i, докато sieve[i] стане 0. Тогава числото i e просто и го отпечатваме.
3) Mаркираме с 1 всички стойности sieve[k], за k = i, 2i, 3i, …, (n/i).i (т.е. всички кратни на i стойности).
4) Ако i <= n, то се връщаме на стъпка 2, иначе приключваме.
—
Това е за днес! Ако видите някоя неточност, сигнализирайте ми. 😉
