Как проверить, является ли число простым



Автор: http://www.swissdelphicenter.ch

function IsPrime(N: Cardinal): Boolean; register;
// test if N is prime, do some small Strong Pseudo Prime test in certain bounds
// copyright (c) 2000 Hagen Reddmann, don't remove
asm
TEST  EAX,1            { Odd(N) ?? }
JNZ   @@1
CMP   EAX,2            { N == 2 ?? }
SETE  AL
RET
@@1:  CMP   EAX,73           { N        JB    @@C }
JE    @@E              { N == 73 ?? }
PUSH  ESI
PUSH  EDI
PUSH  EBX
PUSH  EBP
PUSH  EAX              { save N as Param for @@5 }
LEA   EBP,[EAX - 1]    {  M == N -1, Exponent }
MOV   ECX,32           { calc remaining Bits of M and shift M' }
MOV   ESI,EBP
@@2:  DEC   ECX
SHL   ESI,1
JNC   @@2
PUSH  ECX              { save Bits as Param for @@5 }
PUSH  ESI              {  save M' as Param for @@5 }
CMP   EAX,08A8D7Fh     {  N = 9080191 ?? }
JAE   @@3
// now if (N       MOV   EAX,31
CALL  @@5              { 31^((N-1)(2^s)) mod N }
JC    @@4
MOV   EAX,73           { 73^((N-1)(2^s)) mod N }
PUSH  OFFSET @@4
JMP   @@5
// now if (N @@3:   MOV   EAX,2
CALL  @@5
JC    @@4
MOV   EAX,7
CALL  @@5
JC    @@4
MOV   EAX,61
CALL  @@5
@@4:  SETNC AL
ADD   ESP,4 * 3
POP   EBP
POP   EBX
POP   EDI
POP   ESI
RET
// do a Strong Pseudo Prime Test
@@5:  MOV   EBX,[ESP + 12]     { N on stack }
MOV   ECX,[ESP +  8]     { remaining Bits }
MOV   ESI,[ESP +  4]     { M' }
MOV   EDI,EAX            { T = b, temp. Base }
@@6:  DEC   ECX
MUL   EAX
DIV   EBX
MOV   EAX,EDX
SHL   ESI,1
JNC   @@7
MUL   EDI
DIV   EBX
AND   ESI,ESI
MOV   EAX,EDX
@@7:  JNZ   @@6
CMP   EAX,1      { b^((N -1)(2^s)) mod N ==  1 mod N ?? }
JE    @@A
@@8:  CMP   EAX,EBP    { b^((N -1)(2^s)) mod N == -1 mod N ?? , EBP = N -1 }
JE    @@A
DEC   ECX        { second part to 2^s }
JNG   @@9
MUL   EAX
DIV   EBX
CMP   EDX,1
MOV   EAX,EDX
JNE   @@8
@@9:  STC
@@A:  RET
@@B:  DB    3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71
@@C:  MOV   EDX,OFFSET @@B
MOV   ECX,18
@@D:  CMP   AL,[EDX + ECX]
JE    @@E
DEC   ECX
JNL   @@D
@@E:  SETE  AL
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
if IsPrime(3453451) then
ShowMessage('yes');
end;
{**** Another function ***}
function IsPrime(Prim: Longint): Boolean;
var
Z: Real;
Max: LongInt;
Divisor: LongInt;
begin
Prime := False;
if (Prim and 1) = 0 then
Exit;
Z := Sqrt(Prim);
Max := Trunc(Z) + 1;
Divisor := 3;
while Max > Divisor do
begin
if (Prim mod Divisor) = 0 then
Exit;
Inc(Divisor, 2);
if (Prim mod Divisor) = 0 then
Exit;
Inc(Divisor, 4);
end;
Prime := True;
end;

Далее: Как работать с комплексными числами »»