Как работает алгоритм решета Сундарама для поиска простых чисел?

Алгоритм решета Сундарама предназначен для нахождения всех простых чисел до некоторого целого числа n и был разработан индийским студентом Сундарамом в 1934 году. xgm.guru ru.wikipedia.org

Суть алгоритма: из ряда натуральных чисел от 1 до N исключаются все числа вида i + j + 2ij, где индексы i ≤ j пробегают все натуральные значения, для которых i + j + 2ij ≤ N. xgm.guru ru.wikipedia.org

Далее каждое из оставшихся чисел умножается на 2 и увеличивается на 1. xgm.guru ru.wikipedia.org Полученная в результате последовательность представляет собой все простые числа в отрезке [1, 2N + 1]. infourok.ru xgm.guru

Обоснование алгоритма: алгоритм работает с нечётными натуральными числами, представленными в виде 2m + 1, где m — натуральное число. infourok.ru ru.wikipedia.org Если число 2m + 1 является составным, то оно представляется в виде произведения двух нечётных чисел, больших единицы. infourok.ru xgm.guru Если из ряда натуральных чисел исключить все числа вида 2ij + i + j, то для каждого из оставшихся чисел m число 2m + 1 обязано быть простым. infourok.ru ru.wikipedia.org И, наоборот, если число 2m + 1 является простым, то число m невозможно представить в виде 2ij + i + j, и, таким образом, m не будет исключено в процессе работы алгоритма. infourok.ru ru.wikipedia.org