Решето на Ератостен

Решето на Ератостен е алгоритъм за намиране на всички прости числа в интервала [1, n], където n е произволно естествено число. Алгоритъмът е кръстен на древногръцкия математик Ератостен, на когото е и приписано изобретяването му.

Алгоритъм

Анимация на стъпките на алгоритъма за числата до 120, включително оптимизацията за започване от квадрата на всяко просто число.

Идеята на алгоритъма е, че ако намерим просто число n, то всяко n-то след него няма да е просто.

Описание

Нека разгледаме списък на числата от 1 до n и започвайки от 2, изпълним следните стъпки:

1. Ако числото x е задраскано, преминаваме към следващото
2. Ако числото x не е задраскано, оставяме го така и задраскваме всяко x-то след него.

Накрая всички незадраскани числа, които останат, са прости.

Псевдокод

масивът S се попълва със стойности 'да'
за всяко i от 2 до n //с оптимизация 2. от долу: от 2 до sqrt(n)
   ако S[i] е 'да', тогава
      j = i+i; //с оптимизация 1. от долу: j = i*i;
      докато j <= n 
         S[j] = 'не'; //"задраскване"
         j = j + i

След изпълняването на този алгоритъм, всяко число i, за което S[i] има стойност "да", e просто.

Още

Към алгоритъма може да се приложат следните малки оптимизации:

1. Ако x е незадраскано, то задължително всички кратни на х, по-малки от x², ще са задраскани от стъпките на простите числа по-малки от х. Следователно стигайки до просто число, първото което задраскваме може да е неговия квадрат. Така спестяваме по x-2 стъпки за всяко просто число x, за сметка на повдигане на x на квадрат.
2. Пряко следствие на горното е, че ако в главния цикъл на итерацията си стигнем корена на горната граница n, то задължително всички незадраскани числа след него, до n са прости.