Решето́ Сундара́ма — алгоритм пошуку всіх простих чисел до деякого цілого числа . Алгоритм розробив індійський студент Сундарам () 1934 року.
На практиці алгоритм не застосовується.
Формалізація алгоритму
Із ряду чисел від 1 до N виключаються всі числа, що мають вид
де ,
а кожне із чисел, що залишилися, множиться на 2 і до нього додається 1. Послідовність, що виникає таким чином, є послідовністю непарних простих чисел.
Кількість обчислень можна дещо зменшити, якщо відзначити наступне: в разі i>N/3 Z виходить за межі N вже при j=1, і, відповідно, можна зменшити діапазон значень змінної i.
Складність цього алгоритму становить , що гірше, ніж у решета Ератосфена . Практичної цінності алгоритм не має.
Джерела