Решето Сундара́ма — детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа <math>n</math>. Разработан индийским студентом Сундарамом в 1934 году.
Алгоритм предусматривает исключение из ряда натуральных чисел от 1 до <math>N</math> всех чисел вида:
<math>i+j+2ij</math>,
где индексы <math>i\leqslant j</math> пробегают все натуральные значения, для которых <math>i+j+2ij \leqslant N</math>, а именно значения <math>i=1,\;2,\;\ldots,\;\left\lfloor \frac{\sqrt{2N+1}-1}2\right\rfloor</math> и <math>j=i,\;i+1,\;\ldots,\;\left\lfloor \frac{N-i}{2i+1}\right\rfloor.</math> Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все простые числа в отрезке <math>[1,2N+1]</math>.
Обоснование
Алгоритм работает с нечётными натуральными числами большими единицы, представленными в виде <math>2m+1</math>, где <math>m</math> является натуральным числом.
Если число <math>2m+1</math> является составным, то по определению оно может быть представлено в виде произведения двух нечётных чисел, больших единицы, то есть:
<math>2m+1=(2i+1)(2j+1)</math>, где <math>i</math> и <math>j</math> — натуральные числа. Раскрывая скобки, получаем, что
<math>2m+1=4ij+2i+2j+1</math>, или
<math>2m=4ij+2i+2j</math>, из чего следует, что
<math>m=2ij+i+j</math>.
Таким образом, если из ряда натуральных чисел исключить все числа вида <math>2ij + i + j</math> (<math>1 \leqslant i \leqslant j</math>), то для каждого из оставшихся чисел <math>m</math> число <math>2m+1</math> обязано быть простым. И, наоборот, если число <math>2m+1</math> является простым, то число <math>m</math> невозможно представить в виде <math>2ij+i+j</math> и, таким образом, <math>m</math> не будет исключено в процессе работы алгоритма.
