Решето Эратосфена для нахождения простых чисел

[C_O_D_E]

В последовательности чисел 2, 3, ..., n последовательно вычеркиваем каждое второе число после 2. Первое незачеркнутое число простое (3). Далее вычеркиваем каждое третье число после 3. Первое незачеркнутое число простое (5). Затем вычеркиваем каждое пятое число после 5 и т.д. до тех пор, пока не дойдем до числа, большего корня из n (известно, что если целое положительное число n, неравное 1, не делится ни на одно положительное простое число, не большее корня из n то оно простое). Все числа, которые остаются, простые. Такой метод нахождения простых чисел называется решетом Эратосфена.

Количество простых чисел r не превышает:

Код: Выделить всё

trunc(1.6n/ln(n)+1), если n ≤ 200
trunc(n/(ln(n)-2)+1), если n > 200

[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]

[RReverser]

А разве не проще и не быстрее искать простые числа перебором от 2 до Trunc(Sqrt(N))?:

Код: Выделить всё

function IsSimple(const N:Integer):Boolean;
var I,M:Integer;
begin
M:=Trunc(Sqrt(N));
for I:=2 to M do
if (N mod I)<>0 then
begin
Result:=False;
Exit
end;
Result:=True
end;
procedure FindSimple(const N : Integer; var P : TInteger1DArray);
var I,K:Integer;
begin
SetLength(P,N);
if N=0 then Exit;
P[0]:=1;K:=1;
for I:=2 to N do
if IsSimple(I) then
begin
P[K]:=I;
Inc(K)
end;
SetLength(P,K)
end;

[Naeel Maqsudov]

RReverser, может и проще, но получается больше итераций.
Ведь каждое число проверяется делением на 2, 3... А тут дожход к задаче с другого конца - после вычеркивания каждого второго числа уже не остается чисел которые подлежат проверке делением на 4, 6, 8...

[RReverser]

Пожалуйста, вот оптимизирванный вариант:

Код: Выделить всё

function IsSimple(const N:Integer;const P:TInteger1DArray;const K:Integer):Boolean;
var I,M:Integer;
begin
M:=Trunc(Sqrt(N));
for I:=1 to K-1 do
if (N mod P[I])<>0 then
begin
Result:=False;
Exit
end;
Result:=True
end;
procedure FindSimple(const N : Integer; var P : TInteger1DArray);
var I,K:Integer;
begin
SetLength(P,N);
if N=0 then Exit;
P[0]:=1;K:=1;
for I:=2 to N do
if IsSimple(I,P,K) then
begin
P[K]:=I;
Inc(K)
end;
SetLength(P,K)
end;

В таком случае итераций будет не больше, а в некоторых случаях - и меньше, но код все же проще.

[Medved]

Зависит от постановки задачи и от входящих данных.
1)К примеру, если задача состоит в поиске N первых простых чисел, то решето Эратосфена намного оптимальнее "тупой" проверки каждого числа.
2)Если требуется проверка числа N на простоту, удобнее вариант с "тупой" проверкой
В то же время, если N сравнительно большое, то решето Эратосфена быстрее выполняет функции обеих программ. (при N приблизительно от 10000, проверено)

Также играют роль ограничения. Если имеется ограничение по времени (что очень вероятно) Эратосфен справляется очень хорошо. Если имеется ОЧЕНЬ узкое ограничение по памяти (ОЧЕНЬ маловероятно, не встречал ещё ограничений около 10 кб), то "тупая" проверка - единственный способ.

[C_O_D_E]

Спасибо за здоровую критику Medved, этот код был предаставлен как один из примеров нахождения простых чисел, тем более описан в разделе Алгоритмы.