AlgorithmO #11 - Решето на Ератостен

При днешния алгоритъм е по-интересна имплементацията, отколкото приложението му на ръка. Това е един класически числов алгоритъм за намиране на прости числа в интервал и определено си струва да го добавите към "арсенала" си. 😉

---

Очевидно е, че брадата прави играта... :)

ОПИСАНИЕ:

"Решетото на Ератостен" (да, решетоТО, а не просто решето :)) се използва за намирането на прости числа (т.е, числа, които се делят само на 1 и на себе си) в даден интервал. Името идва от думата "решето" - съд с дъно на дупки, през които отстраняваме ненужното (правили сте си спагети, нали?).

По същия начин, с този алгоритъм премахваме числата, които не отговарят на условието да са прости и след това филтриране получаваме резултата, който ни интересува.

Този алгоритъм е подходящ за малки числа (тъй като за големи става трудно приложим).

АЛГОРИТЪМ:

1. Записваме числата от 2 do 'n' в редица.
2. Намираме първото нездраскано и немаркирано число в редицата.
    Маркираме го като просто число. Да кажем, че това е числото 'i'
    Задраскваме всяко i-то число след 'i' (т.е. задраскваме числата i+i, i+i+i и т.н. до края на интервала)
3. Повтаряме стъпка 2 докато не остане нито едно незадраскано или немаркирано число.         Маркираните са простите числа, които ни интересуват.

ПРИМЕР:

Нека намерим всички прости числа от 2 до 30 (n = 30).

Първо записваме всичките тези числа в редица (между другото, 1 го пропускаме, защото по дефиниция не се счита за просто):

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

Тъй като 2 е първото незадраскано и немаркирано число в редицата, маркираме го като просто (ще го "маркираме" като просто като го оцветим в червен цвят). След това задраскваме всеки 2-ри елемент след него:

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

Тъй като все още имаме незадраскани/нермаркирани елементи, отново трябва да намерим първият незадраскан и немаркиран елемент. Сега това е 3. Задраскваме всички елементи след него, които са кратни на 3:

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

Продължаваме по същата процедура. 4 е задраскан елемент, така че не ни върши работа, но 5 може да бъде маркиран. Задраскваме всеки 5-ти елемент след него: 

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

Следващият елемент, който ще маркираме, е 7, тъй като преди него всички са маркирани или задраскани. Задраскваме всеки 7-ми елемент след него:

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

Е, всъщност не ни се наложи да задраскваме нищо ново... Продължаваме със следващия елемент, който отговаря на горното условие - 11. И за него се оказва, че ще е същото нещо и няма какво да задраскваме. Същото важи за елементите за 13, 17, 19, 23 и 29. Оказва се, че всички те са прости и просто ги маркираме като такива:

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

Стигнаме края - всички числа са или маркирани, или задраскани. Интересуват ни маркираните (оцветените в червено) - те са простите числа, в интервала от 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, иначе приключваме.

---

Това е за днес! Ако видите някоя неточност, сигнализирайте ми. 😉