Q:> 2.3.3.1 Как _быстро_ проверить простое ли число?
A:> Вот программа. Работает действительно очень быстро и достаточно точно.
К сожалению в предыдущем варианте фака в этой программе содержалась
ошибка. Теперь её вроде как нет. =)
{IsPrime.Pas (c) Max Alekseyev, FidoNet: 2:5015/60, e-mail: relf@os2.ru}
{Реализация вероятностного алгоритма Миллера-Рабина с 20 раундами.
Для примера выдает простые на отрезке [1000000000,1000100000]}
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:> Кроме того вот ещё один вариант алгоритма: программа-пример от Зюзика
(хотя вроде как помедленней предыдущего).
Program ZuzikNumbers; {(c) Andrew Lening, 1999}{TurboPascal v7.0}
uses Crt,Dos;
var
n,k,Check1,Check2,SqRoot,Temp,FoundCount: LongInt;
tHour,tMin,tSec,tSec100: Word;
TimeWhenProgRunned,TimeWhenProgStopped: LongInt;
IsBasic1,IsBasic2: Boolean;
begin
Write('Введите N (от 3 до 2*10^9): ');
ReadLn(n);
If (n<3) or (n>2000000000) then begin
WriteLn('Сам дурак. Тут же проверка на тебя есть...');
Halt(1);
end;
FoundCount:=0;
GetTime(tHour,tMin,tSec,tSec100);
TimeWhenProgRunned:=tHour*3600+tMin*60+tSec;
For k:=1 to (n div 6) do begin
Check1:=6*k-1;
Check2:=6*k+1;
IsBasic1:=True;
IsBasic2:=True;
SqRoot:=Round(sqrt(6*k+1));
For Temp:=3 to SqRoot do
If (Check1 mod Temp)=0 then IsBasic1:=False;
For Temp:=3 to SqRoot do
If (Check2 mod Temp)=0 then IsBasic2:=False;
If IsBasic1 then begin
WriteLn(Check1);
Inc(FoundCount);
end;
If IsBasic2 then begin
WriteLn(Check2);
Inc(FoundCount);
end;
end;
GetTime(tHour,tMin,tSec,tSec100);
TimeWhenProgStopped:=tHour*3600+tMin*60+tSec;
WriteLn('Программа нашла ',FoundCount,' простых чисел от 3');
WriteLn('до ',n,' за ',TimeWhenProgStopped-
TimeWhenProgRunned, ' секунд(у,ы).Крюто.');
WriteLn('Самое время что-нибудь нажать');
repeat until KeyPressed;
end.
