Решето Сундарама

Решето́ Сундара́ма — алгоритм пошуку всіх простих чисел до деякого цілого числа $n$. Алгоритм розробив індійський студент Сундарам (Шаблон:Lang-en) 1934 року.

На практиці алгоритм не застосовується.

Формалізація алгоритму

Із ряду чисел від 1 до N виключаються всі числа, що мають вид $Z=i+j+2ij,$

де $i=1,2,3,\dots ,n;j=1,2,3,\dots i$,

а кожне із чисел, що залишилися, множиться на 2 і до нього додається 1. Послідовність, що виникає таким чином, є послідовністю непарних простих чисел.

Кількість обчислень можна дещо зменшити, якщо відзначити наступне: в разі i>N/3 Z виходить за межі N вже при j=1, і, відповідно, можна зменшити діапазон значень змінної i.

Складність цього алгоритму становить $\mathrm{\Theta }(N\ln N)$Шаблон:Джерело?, що гірше, ніж у решета Ератосфена $\mathrm{\Theta }(N\ln \ln N)$. Практичної цінності алгоритм не має.