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

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

Пошаговая демонстрация работы алгоритма для ${\displaystyle N=100}$

Алгоритм предусматривает исключение из ряда натуральных чисел от 1 до ${\displaystyle N}$ всех чисел вида:

${\displaystyle i+j+2ij}$,

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

Обоснование

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

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

${\displaystyle 2m+1=(2i+1)(2j+1)}$, где ${\displaystyle i}$ и ${\displaystyle j}$ — натуральные числа. Раскрывая скобки, получаем, что

${\displaystyle 2m+1=4ij+2i+2j+1}$, или

${\displaystyle 2m=4ij+2i+2j}$, из чего следует, что

${\displaystyle m=2ij+i+j}$.

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

См. также

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

Ссылки

• Б. А. Кордемский. Математическая смекалка. — М.: ГИФМЛ, 1958.
• Baxter, Andrew. «Sundaram’s Sieve». Topics from the History of Cryptography. MU Department of Mathematics.