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

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

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

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

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

,

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

Обоснование

[править | править код]

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

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

, где и  — натуральные числа. Раскрывая скобки, получаем, что
, или
, из чего следует, что
.

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

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