Решето на Ератостен е алгоритъм за намиране на всички прости числа в интервала [1, n], където n е произволно естествено число. Алгоритъмът е кръстен на древногръцкия математик Ератостен, на когото е и приписано изобретяването му.
Алгоритъм
Идеята на алгоритъма е, че ако намерим просто число n, то всяко n-то след него няма да е просто. Описание Нека разгледаме списък на числата от 1 до n и започвайки от 2, изпълним следните стъпки: Ако числото x е задраскано, преминаваме към следващото Ако числото 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 просто.
Още Към алгоритъма може да се приложат следните малки оптимизации:
Ако x е незадраскано, то задължително всички кратни на х, по-малки от x2, ще са задраскани от стъпките на простите числа по-малки от х. Следователно стигайки до просто число, първото което задраскваме може да е неговия квадрат. Така спестяваме по x-2 стъпки за всяко просто число x, за сметка на повдигане на x на квадрат. Пряко следствие на горното е, че ако в главния цикъл на итерацията си стигнем корена на горната граница n, то задължително всички незадраскани числа след него, до n са прости.
Категория:Теория на числата Категория:Алгоритми