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

Нахождение простых чисел используя алгоритма Лемана - C++

Восстановить пароль Регистрация
 
Serega4444
0 / 0 / 0
Регистрация: 12.03.2011
Сообщений: 21
17.03.2014, 18:28     Нахождение простых чисел используя алгоритма Лемана #1
Программа должна находить большие простые числа с помощью алгоритма Лемана. Написал программу, но для большого числа, например 3990851, не работает, это число простое.
Последовательность действий при проверке простоты числа p:
1. Выбрать случайное число а, причем a<p;
2. Вычислить k= a^((p-1) div 2) mod p;
3. Если k ≠ 1 или k≠ (p-1), то рассматриваемое p не является простым.
4. Если k =1 или k= (p-1), то вероятность того, что p не является простым, не более 50
процентов.
5. Попытку (1) – (4) повторить т раз с различными случайными значениями a.
Если результат вычислений равен 1 или (p–1), но не всегда равен 1, то p является простым
числом с вероятностью ошибки 1/2^m.
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
 //---------------------------------------------------------------------------
 
#include <vcl.h>
#include <math.h>
#include <iostream>
using namespace std;
#include <new>
#include <locale>
#pragma hdrstop
 
//---------------------------------------------------------------------------
 
#pragma argsused
int _tmain(int argc, _TCHAR* argv[])
{
long int i,k,a,p,b,x,m,otv,j;
//int N,S;
randomize();
cout << "Vvedite p";
std::cout<<std::endl;
cin >> p;
std::cout<<std::endl;
cout << "Vvedite m ";
std::cout<<std::endl;
cin >> m;
std::cout<<std::endl;
//
otv=1;
b=(p-1) / 2 ;
for (j = 0; j < m; j++) {
 
a=rand() % (p-1) + 1;
cout << "a=" << a;
std::cout<<std::endl;
x=((a % p)*(b % p))% p;
for (i = 3; i <= b; i++) {
x=(x*(a % p))% p;
}
cout<< "k=" << x;
std::cout<<std::endl;
if (x!=1 && x!=p-1) { otv=0;break;}
}
//
std::cout<<std::endl;
std::cout<<std::endl;
if (otv==1) { cout << "Prostoe" ;
 
}else{
cout << "Ne Prostoe" ;
}
//cout « "k=" « a;
std::cout<<std::endl;
system("pause");
return 0;
} //(a ? b) % n = ((a % n) ? (b % n))% n ;
//---------------------------------------------------------------------------
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2014, 18:28     Нахождение простых чисел используя алгоритма Лемана
Посмотрите здесь:

C++ Нахождение простых чисел в массиве
C++ Рекурсивное нахождение простых чисел
Вложенный цикл. Нахождение простых чисел C++
C++ нахождение простых чисел до заданого числа n
Нахождение простых чисел.( C++
C++ Нахождение парных простых чисел с++
Нахождение количества простых чисел в матрице C++
C++ Нахождение простых чисел в С++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 20:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru