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

Решето́ Сундара́ма — детермінований алгоритм знаходження всіх простих чисел до деякого цілого числа $\quad n$ . Алгоритм було розроблено індійським студентом С. П. Сундарамом в 1934 році.

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

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

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

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

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.