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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

,

где индексы пробегают все натуральные значения, для которых , а именно значения и Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все простые числа в отрезке .

Обоснование[править | править код]

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

Если число является составным, то оно представляется в виде произведения двух нечётных чисел больших единицы, то есть:

,

где и  — натуральные числа, что также равносильно соотношению:

.

Таким образом, если из ряда натуральных чисел исключить все числа вида (), то для каждого из оставшихся чисел число обязано быть простым. И, наоборот, если число является простым, то число невозможно представить в виде и, таким образом, не будет исключено в процессе работы алгоритма.

Пример программы на языке Си[править | править код]

#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;
}

См. также[править | править код]

Ссылки[править | править код]