|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 11 Nov 2002 23:53:58
To : Oleg Zhigalov
Subject : Простые числа
--------------------------------------------------------------------------------
Replying to a message of Oleg Zhigalov to All:
OZ> есть у всезнающего Алл алгоритм для определения числа на предмет
OZ> простое оно или нет, желательно на Паскале, срочно. Буду премного
OZ> благодарен.
===cut===
{IsPrime.Pas ver. 2.0 (c) Max Alekseyev <relf[at]os2.ru>, 2:5015/60@FidoNet}
{Реализация вероятностного алгоритма Миллера-Рабина с 20 раундами.
Для примера выдает простые на отрезке [1000000000,1000100000].
Вероятность ошибки (то, что составное число будет названо простым) меньше
4^(-Rounds).}
const Rounds=20;
function mulmod(x,y,m:longint):longint; assembler;
asm
{$IFDEF USE32}
mov eax,x
mul y
div m
mov eax,edx
{$ELSE}
db $66; mov ax,word ptr x
db $66; mul word ptr y
db $66; div word ptr m
mov ax,dx
db $66; shr dx,16
{$ENDIF}
end;
function powmod(x,a,m:longint):longint;
var r:longint;
begin
r:=1;
while a>0 do
begin
if odd(a) then r:=mulmod(r,x,m);
a:=a shr 1;
x:=mulmod(x,x,m);
end;
powmod:=r;
end;
function isprime(p:longint):boolean;
var q,i,a:longint;
begin
if odd(p) and (p>1) then
begin
isprime:=true;
q:=p-1;
repeat q:=q shr 1; until odd(q);
for i:=1 to Rounds do
begin
{$IFDEF USE32} a:=Random(p-2)+2; {$ELSE} a:=2+Trunc(Random*(p-2)); {$ENDIF}
if powmod(a,p-1,p)<>1 then
begin
isprime:=false; break;
end;
a:=powmod(a,q,p);
if a<>1 then
begin
while (a<>1) and (a<>p-1) do a:=mulmod(a,a,p);
if a=1 then
begin
isprime:=false; break;
end;
end;
end;
end else isprime:=(p=2);
end;
var t:longint;
begin
Randomize; {Don't forget to reset Random Generator!}
for t:=1000000000 to 1000100000 do if isprime(t) then writeln(t);
end.
===cut===
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
