whats new ¦  programming tips ¦  indy articles ¦  intraweb articles ¦  informations ¦  links ¦  interviews
 misc ¦  tutorials ¦  Add&Win Game

Tips (1548)

Database (90)
Files (137)
Forms (107)
Graphic (116)
IDE (21)
Indy (5)
Internet / LAN (131)
IntraWeb (0)
Math (76)
Misc (127)
Multimedia (45)
Objects/
ActiveX (51)

OpenTools API (3)
Printing (35)
Strings (83)
System (268)
VCL (243)

Top15

Tips sort by
component


Search Tip

Add new Tip

Add&Win Game

Advertising

20 Visitors Online


 
...check if a number is prime?
Autor: Hagen Reddmann
[ Print tip ]  

Tip Rating (21):  
     


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;


 

Rate this tip:

poor
very good


Copyright © by SwissDelphiCenter.ch
All trademarks are the sole property of their respective owners