Delphi World - Как проверить, является ли число простым
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Как проверить, является ли число простым

Автор: 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;
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования