Решето Эратосфена для нахождения простых чисел
Добавлено: 26 окт 2008, 11:37
В последовательности чисел 2, 3, ..., n последовательно вычеркиваем каждое второе число после 2. Первое незачеркнутое число простое (3). Далее вычеркиваем каждое третье число после 3. Первое незачеркнутое число простое (5). Затем вычеркиваем каждое пятое число после 5 и т.д. до тех пор, пока не дойдем до числа, большего корня из n (известно, что если целое положительное число n, неравное 1, не делится ни на одно положительное простое число, не большее корня из n то оно простое). Все числа, которые остаются, простые. Такой метод нахождения простых чисел называется решетом Эратосфена.
Количество простых чисел r не превышает:
[syntax=Delphi]
(*************************************************************************
Процедура заполняет массив P простыми числами меньшими n,
элемент массива является последним, если следующий за ним
элемент равен 0.
*************************************************************************)
procedure EratosthenesSieve(const N : Integer; var P : TInteger1DArray);
var
C : Boolean;
I : Integer;
J : Integer;
K : Integer;
R : Integer;
S : Double;
begin
if N>200 then
begin
R := trunc(N/(Ln(N)-2)+1);
end
else
begin
R := trunc(1.6*N/Ln(N)+1);
end;
SetLength(P, R+1);
P[1] := 1;
P[2] := 2;
P[3] := 3;
i := 4;
repeat
P := 0;
i := i+1;
until not (i<=r);
j := 3;
k := 3;
repeat
i := 2;
s := sqrt(k);
c := True;
repeat
i := i+1;
if P>S then
begin
P[j] := k;
j := j+1;
c := False;
end;
until not ((trunc(k/P)*P<>K) and C);
k := k+2;
until not (k<=n);
end;
[/syntax]
Количество простых чисел r не превышает:
Код: Выделить всё
trunc(1.6n/ln(n)+1), если n ≤ 200
trunc(n/(ln(n)-2)+1), если n > 200
(*************************************************************************
Процедура заполняет массив P простыми числами меньшими n,
элемент массива является последним, если следующий за ним
элемент равен 0.
*************************************************************************)
procedure EratosthenesSieve(const N : Integer; var P : TInteger1DArray);
var
C : Boolean;
I : Integer;
J : Integer;
K : Integer;
R : Integer;
S : Double;
begin
if N>200 then
begin
R := trunc(N/(Ln(N)-2)+1);
end
else
begin
R := trunc(1.6*N/Ln(N)+1);
end;
SetLength(P, R+1);
P[1] := 1;
P[2] := 2;
P[3] := 3;
i := 4;
repeat
P := 0;
i := i+1;
until not (i<=r);
j := 3;
k := 3;
repeat
i := 2;
s := sqrt(k);
c := True;
repeat
i := i+1;
if P>S then
begin
P[j] := k;
j := j+1;
c := False;
end;
until not ((trunc(k/P)*P<>K) and C);
k := k+2;
until not (k<=n);
end;
[/syntax]