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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В математиці решето́ Сундара́ма — детермінований алгоритм знахождення всіх простих чисел до деякого цілого числа \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}}).

Статті з математики, пов'язані з числами

Число | Натуральні числа | Цілі числа | Раціональні числа | Ірраціональні числа | Constructible numbers | Алгебраїчні числа | Трансцендентні числа | Computable numbers | Дійсні числа | Комплексні числа | Подвійні числа | Дуальні числа | Бікомплексні числа | Гіперкомплексні числа | Кватерніони | Октоніони | Седеніони | Superreal numbers | Hyperreal numbers | Surreal numbers | Nominal numbers | Ординальні числа | Кардинальні числа | P-адичні числа | Послідовності натуральних чисел | Математичні константи | Великі числа | Нескінченність