Mega Code Archive
How to check if a number is prime
<![CDATA[
Title: How to check if a number is prime
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;
]]>