ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      12 Mar 2002  16:11:36
 To : fat
 Subject : Простые числа
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of fat to All:
 
  f> Есть где-нибудь таблицы простых чисел?
  f> Или быстрые алгоритмы определения простоты числа?
 
 Вероятностный тест Милера-Рабина. Вот примерная реализация на паскале для типа
 longint. Для больших чисел все то же самое, только реализуется на длинной
 арифметике.
 
 ===cut===
      {IsPrime.Pas (c) Max Alekseyev, FidoNet: 2:5015/60, e-mail: relf@os2.ru}
      {Реализация вероятностного алгоритма Миллера-Рабина с 20 раундами.
      Для примера выдает простые на отрезке [1000000000,1000100000]}
 
      function mulmod(x,y,m:longint):longint; assembler;
       asm
         mov eax,x
         mul y
         div m
         mov eax,edx
       end;
 
      function powmod(x,a,m:longint):longint;
       var
         r:longint;
       begin
        r:=1;
        while a>0 do
        begin
          if odd(a) then r:=mulmod(r,x,m);
          a:=a shr 1;
          x:=mulmod(x,x,m);
        end;
        powmod:=r;
      end;
 
      function isprime(p:longint):boolean;
      var q,i,a:longint;
      const rounds=20;
      begin
      if odd(p) then
      begin
        isprime:=true;
        q:=p-1;
        while not odd(q) do q:=q shr 1;
        for i:=1 to rounds do
        begin
          a:=Random(p-2)+2;
          if powmod(a,p-1,p)<>1 then
          begin
            isprime:=false;
            break;
          end;
          a:=powmod(a,q,p);
          if a<>1 then
          begin
            while (a<>1) and (a<>p-1) do a:=mulmod(a,a,p);
            if a=1 then
            begin
              isprime:=false;
              break;
            end;
          end;
        end;
      end else isprime:=(p=2);
      end;
 
      var t:longint;
      begin
        Randomize;
        for t:=1000000000 to 1000100000 do if isprime(t) then writeln(t);
      end.
 ===cut===
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.7
  * Origin:  (2:5015/60)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Простые числа   fat   12 Mar 2002 21:26:18   Re: Простые числа   Roman Ilyin   13 Mar 2002 01:43:14   Hа: Простые числа   Ђ«ҐЄбҐ© „.   13 Mar 2002 15:14:16   Простые числа   Max Alekseyev   12 Mar 2002 16:11:36