PDA

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



C_O_D_E
26.10.2008, 11:37
В последовательности чисел 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



(************************************************* ************************
Процедура заполняет массив 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[i] := 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[i]>S then
begin
P[j] := k;
j := j+1;
c := False;
end;
until not ((trunc(k/P[i])*P[i]<>K) and C);
k := k+2;
until not (k<=n);
end;

RReverser
01.11.2008, 16:29
А разве не проще и не быстрее искать простые числа перебором от 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
02.11.2008, 14:09
RReverser, может и проще, но получается больше итераций.
Ведь каждое число проверяется делением на 2, 3... А тут дожход к задаче с другого конца - после вычеркивания каждого второго числа уже не остается чисел которые подлежат проверке делением на 4, 6, 8...

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

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
14.11.2008, 19:48
Зависит от постановки задачи и от входящих данных.
1)К примеру, если задача состоит в поиске N первых простых чисел, то решето Эратосфена намного оптимальнее "тупой" проверки каждого числа.
2)Если требуется проверка числа N на простоту, удобнее вариант с "тупой" проверкой
В то же время, если N сравнительно большое, то решето Эратосфена быстрее выполняет функции обеих программ. (при N приблизительно от 10000, проверено)

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

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