Решето на Ератостен
Решето на Ератостен е алгоритъм за намиране на всички прости числа в интервала [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 са прости.

Теория на числата
Алгоритми