WikiSort.ru - Не сортированное

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

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

${\displaystyle i+j+2ij}$ ,

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

Обоснование

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

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

${\displaystyle 2m+1=(2i+1)(2j+1)}$ ,

где ${\displaystyle i}$ и ${\displaystyle j}$  — натуральные числа, что также равносильно соотношению:

${\displaystyle m=2ij+i+j}$ .

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

#include <stdio.h>
int main(void) {
    int i,j,n;
    scanf("%d",&n);
    char a[n];
    
    for (i=1; i<=n; i++)
        a[i]=1;

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

См. также

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

Ссылки

Имеется викиучебник по теме
«Программные реализации решета Сундарама»

• Б. А. Кордемский. Математическая смекалка. — М.: ГИФМЛ, 1958.