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

Решето́ Сундара́ма — алгоритм пошуку всіх простих чисел до деякого цілого числа ${\displaystyle \quad n}$. Алгоритм розробив індійський студент Сундарам (англ. S. P. Sundaram) 1934 року.

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

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

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

де ${\displaystyle i=1,\;2,\;3,\;\ldots ,\;n;\quad j=1,\;2,\;3,\;\ldots \,\;i}$,

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

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

Складність цього алгоритму становить ${\displaystyle \Theta (N\ln {N})}$^[], що гірше, ніж у решета Ератосфена ${\displaystyle \Theta (N\ln {\ln {N}})}$. Практичної цінності алгоритм не має.

Джерела

1. Andrew Baxter. . History of Cryptography. MU Department of Mathematics. Архів оригіналу за 12 серпня 2011. Процитовано 29 липня 2023.