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