«

»

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

Решето Сундарама – алгоритм поиска всех простых чисел в некотором заданном диапазоне. Он был разработан в 1934 году ныне безызвестным студентом из Индии С. П. Сундарамом.

Принцип работы алгоритма Сундарама сводится, как и в его знаменитом предшественнике, к последовательному отсеиванию всех ненужных чисел. Но у него есть одна небольшая особенность: результатом работы алгоритма будет последовательность простых чисел из диапазона от 2 до удвоенного значения граничного числа. Допустим необходимо получить все простые числа до некоторого N, тогда выходными данными будут все простые числа от 2 до 2N+1.

Решето Сундарама из ряда натуральных чисел, не превышающих N, исключает числа вида 2ij+i+j. Результат данного выражения, ни при каких значениях входящих в него переменных, не превышает N (2ij+i+j≤N).  Соблюдая это условие, а также то, что i всегда меньше или равно j, переменные i и j пробегают все натуральные значения из множеств:

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

После исключения всех ненужных чисел необходимо увеличить каждое оставшиеся число в два раза и прибавить единицу (2i+1). Итоговое множество будет содержать числа: 2, 3, …, 2N+1.

Код программы на C++:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include "stdafx.h"
#include <iostream>
using namespace std;
//Решето Сундарама
void Sundaram(bool A[], int N)
{
int i, j;
for (i=1; i<=N; i++) A[i]=true;
i=1; j=1;
while ((2*i*j+i+j)<=N)
{
while (j<=(N-i)/(2*i+1))
{
A[2*i*j+i+j]=false;
j++;
}
i++;
j=i;
}
for (i=1; i<=N; i++)
if (A[i]) cout<<2*i+1<<" ";
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
int N, i, j;
bool A[1000];
cout<<"N > "; cin>>N;
cout<<"Простые числа: 2 ";
Sundaram(A, N);
system("pause>>void");
}

 

Код программы на Pascal:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
program SieveOfSundaram;
uses crt;
type arr=array [1..1000] of boolean;
var
N: integer;
A: arr;
{Решето Сундарама}
procedure Sundaram(A: arr; N: integer);
var i, j: integer;
begin
for i:=1 to N do A[i]:=true;
i:=1; j:=1;
while (2*i*j+i+j)<=n do
begin
while j<=(N-i)/(2*i+1) do
begin
A[2*i*j+i+j]:=false;
j:=j+1;
end;
i:=i+1;
j:=i;
end;
write(2, ' ');
for i:=1 to n do
if A[i] then write(2*i+1, ' ');
end;
{основной блок программы}
begin
write('N > '); read(n);
writeln('Простые числа:');
Sundaram(A, N);
end.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *