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

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

Описание

Из ряда натуральных чисел от 1 до N исключаются все числа вида

$i+j+2ij,$

где индексы $i\leq j$ пробегают все натуральные значения, для которых $i+j+2ij \leq N$, а именно значения $i=1,\;2,\;\ldots,\;\left\lfloor \frac{\sqrt{2N+1}-1}2\right\rfloor$ и $j=i,\;i+1,\;\ldots,\;\left\lfloor \frac{N-i}{2i+1}\right\rfloor.$ Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все нечётные простые числа в отрезке [1,2N+1].

Обоснование

Алгоритм работает с нечётными натуральными числами большими единицы, представленными в виде 2m+1, где m является натуральным числом.

Если число 2m+1 является составным, то оно представляется в виде произведения двух нечётных чисел больших единицы, то есть:

2m+1 = (2i+1)(2j+1)

где i и j — натуральные числа, что также равносильно соотношению:

m = 2ij+i+j.

Таким образом, если из ряда натуральных чисел исключить все числа вида $2ij + i + j$, $1 \le i \le j$, то для каждого из оставшихся чисел m число 2m+1 обязано быть простым. И, наоборот, если число 2m+1 является простым, то число m невозможно представить в виде 2ij+i+j и, таким образом, m не будет исключено в процессе работы алгоритма.

См. также

• Корекурсия
• Решето Эратосфена
• Решето Аткина

Ссылки

Имеется викиучебник по теме
«Программные реализации решета Сундарама»

• Б. А. Кордемский Математическая смекалка. — М.: ГИФМЛ, 1958.
• Решение С. П. Сундарама
• Формализация этого метода
• Простые числа