Как проверить, является ли число простым ```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;```
Проект Delphi World © Выпуск 2002 - 2024
Автор проекта: USU Software
Вы можете выкупить этот проект.