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

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

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

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

$i+j+2ij$,

где индексы $i\leqslant j$ пробегают все натуральные значения, для которых $i+j+2ij\leqslant N$, а именно значения $i=1,\;2,\;\ldots ,\;\left\lfloor {\frac {{\sqrt {2N+1}}-1}{2}}\right\rfloor$ и $j=i,\;i+1,\;\ldots ,\;\left\lfloor {\frac {N-i}{2i+1}}\right\rfloor .$ Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все простые числа в отрезке $[1,2N+1]$.

Обоснование

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

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

$2m+1=(2i+1)(2j+1)$, где $i$ и $j$ — натуральные числа. Раскрывая скобки, получаем, что

$2m+1=4ij+2i+2j+1$, или

$2m=4ij+2i+2j$, из чего следует, что

$m=2ij+i+j$.

Таким образом, если из ряда натуральных чисел исключить все числа вида $2ij+i+j$ ($1\leqslant i\leqslant j$), то для каждого из оставшихся чисел $m$ число $2m+1$ обязано быть простым. И, наоборот, если число $2m+1$ является простым, то число $m$ невозможно представить в виде $2ij+i+j$ и, таким образом, $m$ не будет исключено в процессе работы алгоритма.

stdio.h> int main(void) {

   int i,j,n,ind;
   scanf("%d",&n)
   char a[n+1];
   
   for (i=1; i<=n; i++)
       a[i]=1;

   for(i=1;2*i*(i+1)<n;i+)
       for(j=i;ind=2*i*j+i+j,ind<=n;j++)
           a[ind]=0;
   
   for(i=1;i<=n;i++)
       if(a[i])
           printf("%d ",2*i+1);
   return 0;

} </source>

См. также

• Корекурсия
• Решето Эратосфена
• Решето Аткина

Ссылки

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