Q:> 2.3.3.1 Як _бистро_ перевірити просте число?
A:> Ось програма. Працює дійсно дуже швидко і досить точно. На жаль в попередньому варіанті фака в цій програмі містилася помилка. Тепер її ніби як немає. =)
function mulmod (x, y, m: longint): longint; assembler;
asm
mov eax, x
mul y
div m
mov eax, edx
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;
const rounds = 20;
begin
if odd (p) then
begin
isprime: = true;
q: = p-1;
while not odd (q) do q: = q shr 1;
for i: = 1 to rounds do
begin
a: = Random (p-2) +2;
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;
for t: = 1000000000 to 1000100000 do if isprime (t) then writeln (t);
end.
A:> Крім того ось ще один варіант алгоритму: програма-приклад від Зюзік
(Хоча ніби як повільніше попереднього).
На першу сторінку