Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

тест миллера-рабина, pascal -> c++ - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перевод целого десятичного числа в двоичною систему числения http://www.cyberforum.ru/cpp-beginners/thread27815.html
составит програму перевода целого десятичног числа в двоичною систему числения
C++ Как упростить работу с case Подскажите пожалуйста как сделать чтобы при вводе чисел от 1 до 20 был один case, от 21 до 40 второй , ну чтобы не вводить много раз : case 1 case 2 case 3 и т.д. а сразу от 1 до 3 http://www.cyberforum.ru/cpp-beginners/thread27811.html
Не удалось создать командную строку для инструмента "VCCLCompilerTool". C++
Создаю пустой проект Приложение MFC на основе диалоговых окон запускаю под Win32, всё нормально вылетает пустое окно с кнопками (ОК Cancel), меняю платформу под 5й мобайл, и не запускается. 1>34 :...
Настройка MS VS 2008 C++
Привет всем! Просмотрев многие темы на этом форуме и не только я увидел, что некоторые решение проблем полагают в изменение настроек студии. Напишите как правильно ёё настроить. Заранее благодарен...
C++ Напечатать в возрастающем порядке все трехзначные числа http://www.cyberforum.ru/cpp-beginners/thread27802.html
напечатать в возрастающем порядке все трехзначные числа,в десятичной записи которых нет одинаковых цыфр
C++ Проблемы с русским в MS VS 2008 Привет всем! У меня есть проблема в MS VS 2008 с русским. Если в коде написать комментарий или строку на русском, то после сохранения, закрытия и открытия исходника, то вместо русских букв иероглифы... подробнее

Показать сообщение отдельно
amiserio
1 / 1 / 0
Регистрация: 18.10.2008
Сообщений: 11

тест миллера-рабина, pascal -> c++ - C++

28.03.2009, 16:14. Просмотров 8278. Ответов 10
Метки (Все метки)

собсно, кто знает дельфи и с++, обьясните где я не прав пожалуйста=)
дельфи:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
{IsPrime.Pas ver. 2.0 (c) Max Alekseyev <relf@os2.ru>, 2:5015/60@FidoNet}
{Реализация вероятностного алгоритма Миллера-Рабина с 20 раундами.
Для примера выдает простые на отрезке [1000000000,1000100000].
Вероятность ошибки (то, что составное число будет названо простым) меньше
4^(-Rounds).}
 
const Rounds=20;
 
function mulmod(x,y,m:longint):longint; assembler;
asm
{$IFDEF USE32}
  mov eax,x
  mul y
  div m
  mov eax,edx
{$ELSE}
  db $66; mov ax,word ptr x
  db $66; mul word ptr y
  db $66; div word ptr m
  mov ax,dx
  db $66; shr dx,16
{$ENDIF}
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;
begin
if odd(p) and (p>1) then
begin
  isprime:=true;
  q:=p-1;
  repeat q:=q shr 1; until odd(q);
  for i:=1 to Rounds do
  begin
    {$IFDEF USE32}
     a:=Random(p-2)+2; {$ELSE} a:=2+Trunc(Random*(p-2)); {$ENDIF}
    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; {Don't forget to reset Random Generator!}
  for t:=1000000000 to 1000100000 do if isprime(t) then writeln(t);end.
с++, где large - всеравно что unsigned int:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
int rounds=20;
large mulmod(large x,large y,large m)
{
    return (x*y)%m;
}
large powmod(large x,large a,large m)
{
    large r=1;
    while(a>0)
    {
        if(a%2==0) 
           r=mulmod(r,x,m);
        a=a>>1; 
        x=mulmod(x,x,m);
    }
    return r;
}
 
bool isprime(large p)
{
    large q,a;
    int i;
    cl_randex rand;
    rand.set_max("100000000000"); // макс число для генератора сл. чисел
    if(p%2==0 && p>1)
    {
         q=p-1;
         do q=q>>1; while(q%2==0);
         for(i=1; i<rounds; i++)
         {
               a=rand.lgen(p-2)+2; //rand.lgen - генератор сл. чисел
               if(powmod(a,p-1,p)!=1)
               {
                     return false;
                     break;
               }
               a=powmod(a,q,p);
               if(a!=1)
               {
                    while(a!=1 && a!=p-1) a=mulmod(a,a,p);
                    if(a==1)
                    {
                       return false;
                       break;
                    }
               }
          }
          return true;
    }
    else
     return false;
}
 
int _tmain()
{
  large t;
  for(t="1000000000";t<"1000100000";t+="1")
  {
      if(isprime(t))
         cout<<"t="<<t<<endl;
  }
  system("pause");
  return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru