|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 16 Sep 2001 16:07:56
To : Alexander Topolskiy
Subject : Is it a simple number: 3^x-2; xE[1,1000000]
--------------------------------------------------------------------------------
Replying to a message of Alexander Topolskiy to Max Alekseyev:
DS>>> написать программу для определения, является ли число
DS>>> 3^x-2 простым. x лежит в пределах [1, 1000000] (большой, короче). У
DS>>> кого-нибудь есть идеи по этому поводу?
MA>> Универсальное средство - тест Милера-Рабина.
AT> А подробней?
Hа http://www.mccme.ru/free-books/matpros3.html
берешь статью Ю.В.Hестеренко "Алгоритмические проблемы теории чисел"
Там все подробно расписано.
Hиже идет примерная программа.
Кстати, простое число по-английски - это "prime" и никак иначе.
===cut===
{IsPrime.Pas ver. 2.0 (c) Max Alekseyev <relf@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.6
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
