Processing math: 100%

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

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

Описание


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

i+j+2ij,
 где индексы ij пробегают все натуральные значения, для которыхi+j+2ijN, а именно значенияi=1,2,,2N+112 иj=i,i+1,,Ni2i+1. Затемкаждое из оставшихся чисел умножается на 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, 1ij, то для каждого изоставшихся чисел m число 2m+1 обязано быть простым. И,наоборот, если число 2m+1 является простым, то число mневозможно представить в виде 2ij+i+j и, таким образом, m небудет исключено в процессе работы алгоритма.