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

Previous  Top  Next

    
 

 

 

Code:

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;

©Drkb::04086

Взято с сайта http://www.swissdelphicenter.ch/en/tipsindex.php