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

Решето Сундара́ма — детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа $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$ не будет исключено в процессе работы алгоритма.

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    bool a[n + 1];
    
    for(int i = 1; i <= n; i++) {
        a[i] = true;
    }

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

Пример реализации на python3.8

n = int(input())

sc = set(range(1, n + 1))

for i in range(1, int((((2 * n + 1)**0.5) - 1) / 2) + 1):
    for j in range(i, (n - 1) // (2 * i + 1) + 1):
        sc.remove(i + j + 2 * i * j)

sc = sorted(i * 2 + 1 for i in sc)

print(sc)

См. также

Ссылки

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.