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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание[править | править вики-текст]

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

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

где индексы пробегают все натуральные значения, для которых , а именно значения и Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все нечётные простые числа в отрезке .

Обоснование[править | править вики-текст]

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

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

,

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

.

Таким образом, если из ряда натуральных чисел исключить все числа вида , , то для каждого из оставшихся чисел m число обязано быть простым. И, наоборот, если число является простым, то число m невозможно представить в виде и, таким образом, m не будет исключено в процессе работы алгоритма.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]