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

Delphi , Синтаксис , Математика

Автор: 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, которая проверяет, является ли число простым или нет. В ней есть два функционала для этого: IsPrime и другой IsPrime.

Первая функция (IsPrime): Эта функция использует тест псевдопростых чисел для определения, является ли вводное число простым. Она написана на языке ассемблера и имеет некоторые ограничения, такие как проверка только до 9080191.

Работает она следующим образом:

1. Сначала она проверяет, является ли вводное число N четным или нечетным.
2. Если N четно, то она возвращает false немедленно (поскольку четные числа не являются простыми).
3. Затем она рассчитывает остаток от деления (N-1) / 2^s, где s - количество бит в N.
4. Она проверяет, является ли этот остаток меньше или равен 73. Если так, то она выполняет тест псевдопростых чисел.
5. Во время этого теста она рассчитывает значение b = (a^(N-1) * 2^s) mod N для различных значений a и проверяет, является ли результат конгруентен 1 или -1 по модулю N.
6. Если все эти тесты проходят, то она возвращает true; иначе, она возвращает false.

Вторая функция (IsPrime): Эта функция использует более простой подход: деление на пробел. Она написана на языке Pascal и проверяет делимость до квадрата корня из вводного числа.

Работает она следующим образом:

1. Сначала она проверяет, является ли вводное число Prim делимым на 2.
2. Если нет, то она рассчитывает квадратный корень из Prim.
3. Затем она итерирует от 3 до этого квадрата, увеличивая на 2 каждый раз (поскольку все четные числа уже проверены).
4. Для каждого делителя она проверяет, является ли Prim делимым этим делителем.
5. Если делитель найден, то она возвращает false немедленно; иначе, она продолжает до квадрата корня.
6. Если не найдено делителей, то она возвращает true.

Использование: Первая функция используется в обработчике события Button1Click для проверки, является ли число 3453451 простым или нет.

Замечания:

• Первая функция имеет некоторые ограничения и может не быть подходящей для больших чисел.
• Вторая функция более проста, но менее эффективна для очень больших чисел (поскольку она выполняет деление на пробел до квадрата корня из вводного числа).
• Обе функции имеют различные подходы к проверке простоты и есть много других способов выполнить это в языках программирования.

Как проверить, является ли число простым: статья описывает несколько способов проверки простоты целого числа, включая функцию IsPrime на языке Delphi и алгоритм Strong Pseudo Prime.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Математика ::