Простые числа

← →
JediMaster (2004-02-06 13:00) [0]

Подскажите алгоритм для поиска простых чисел, нужно найти числа от 0 до 15000, простой метод(искать делители) не пойдет.
За ранее спасибо :)

← →
Sandman25 © (2004-02-06 13:03) [1]

Вычеркиваете из списка кандидатов всех, которые делятся на 2. Потом те, которые делятся на минимальное из оставшихся (кроме него самого). И так пока не дойдете до конца.

PS. "Вычеркнуть четные" можно при занесении в массив, конечно.

← →
MBo © (2004-02-06 13:04) [2]

Просто заноси найденные простые числа в список, и проверяй делимость только на них.

← →
MV (2004-02-06 13:12) [3]

Алгиритма нэт! Просто заноси найденные простые числа в список, и проверяй делимость только на них. И все!

← →
Sandman25 © (2004-02-06 13:21) [4]

const N = 15000;

for I := 2 to N do
A[I] := N;
Current := 2;
while (Current <= N) do
begin
if A[Current] <> 0 then
for J := 2 TO N div I do
A[J*Current] := 0;
Inc(Current);
end;

for I := 2 to N do
if A[I] <> 0 then
showmessage(inttostr(I));

← →
Sandman25 © (2004-02-06 13:24) [5]

А еще лучше так:
const N = 15000;

fillchar(@A[2], SizeOf(A[2])*(N-1), 1);
for Current := 2 to N do
begin
if A[Current] <> 0 then
for J := 2 TO N div I do
A[J*Current] := 0;
end;

for I := 2 to N do
if A[I] <> 0 then
showmessage(inttostr(I));

← →
pasha_golub © (2004-02-06 13:25) [6]

Решето Эратосфена.

Реализайций море. Можно с массивом, но накладно с памятью, а можно с битовыми операциями. Дык, прикинем... 15000 / 8 = 1875 байт потребуется, для нынешних машин это пшык. Удачи.

← →
Sandman25 © (2004-02-06 13:27) [7]

Решето Эратосфена.

Точно. А то не мог вспомнить название :)

← →
Serginio666 (2004-02-06 13:44) [8]

Function TNewInt32Hash.ProstoeChislo(v: Cardinal): Cardinal;
VAR i:Cardinal;
Find:Boolean;
Begin

Result:=v or 1;
Find:=true;

While true do
Begin
i:=3;

While i<Trunc(Sqrt(result)) do
Begin
If (result mod i)= 0 Then
Begin
Find:=false;
break
end
Else inc(i,2);
end;

If Find Then
exit
else
begin
Find:=true;
inc(result,2);
end;
end;

End;

← →
Brahman © (2004-02-06 14:07) [9]

Проще и быть не может:)

for i:=0 to N-1 do A[i] := i;
num:=0;
for i := 2 to N-1 do begin
if A[i] <> 0 then inc(num);
j := i + i;
while j <= N-1 do begin
A[j] := 0;
j := j + i;
end;
end;

← →
JediMaster (2004-02-06 14:13) [10]

Нужно не от 0 до 15000, а первые 15000 чисел.
Всем спасибо за помощь :)

← →
Serginio666 (2004-02-06 14:15) [11]

← →
Serginio666 (2004-02-06 15:07) [12]

http://www.rsdn.ru/Forum/Message.aspx?mid=48059&only=1

>Нужно не от 0 до 15000, а первые 15000 чисел.
по формулам Чебышева можно оценить величину N-ого простого. после этого решето Эратосфена. например, как в [9] Brahman. только если вместо
j := i + i;
делать
j := i * i;
то быстрее получится.

Простые числа Найти похожие ветки