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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Модуль большого числа http://www.cyberforum.ru/cpp-beginners/thread1121985.html
Доброго времени суток. Вот такая проблема. Имеется большое число, тип long double, нужно найти остаток от деления на 43, к примеру. (x%43) Проблема в том, что для этого нужен целочисленный тип данных. Число слишком большое и оно вне пределов этого типа. Есть ли альтернатива этой операции в long double или есть другие способы нахождения остатка? Спасибо.
C++ Переправа через горы В универе задали задачу, никак не могу решить. Помогите, кто разбирается в алгоритме или хотя бы подкиньте идею. Заранее спасибо. Переправа через горы разбита на несколько этапов. Известно расстояние между этапами и высота каждого перевалочного пункта над уровнем моря. Определить: a) длину самого большого подъема; b) сколько этапов в самом длинном подъеме; c) самый большой подъем, его длину... http://www.cyberforum.ru/cpp-beginners/thread1121983.html
Дана строка в которой будет находится команда на ассемблере. Построчно разбить эту команду на лексе C++
Подскажите пожалуйста что делать ! У меня такое задание : Дана строка в которой будет находится какая-нибудь команда на ассемблере Например : m1:mov ax,bx;comments Нужно построчно разбить эту команду на лексемы (без раздилителей), чтобы все это выглядело вот так m1 mov ax bx comments Так же проблема заключается в том, что мой препод может потребовать написать строку в которой может...
Посоветуйте компилятор C++
Задания на мои лабораторные роботы проверяются на сервере одного сайта. Пишу в Visual Studio и программа компилируется, а вот на сервере нет. Преподаватель посоветовала поставить самый простой консольный компилятор и на нем все отладить, мол Студия что-то сама подключает в добавок. Когда на сервере выбираю компилятор, там выставляю Visual C++ 9.0. Подскажите где такой скачать, и как с ним...
C++ Доступ к переменной только из двух функций. Возможно ли это? http://www.cyberforum.ru/cpp-beginners/thread1121920.html
Две функции, не члены класса, одна из них должна писать в переменную, другая эту переменную читать и больше ни где эта переменная должна быть не доступна. Инфа должна в этой переменной сохраняться между вызовами второй функции.
C++ Функция - rand Здравствуйте. Проблема - нужно сгенерировать случайное число из области чисел введённых в переменную. Допустим, я создаю переменную: int a; cout << " Введите значение числа 'a':\n"; cin >> a;Далее, допустим, я ввёл число 555 и мне из этого числа надо сгенерировать одно любое, от 1 до 555. Написал цикл для этого, а он мне выдаёт. Всё внимание на последнюю строку и числа в ней. подробнее

Показать сообщение отдельно
Serega4444
0 / 0 / 0
Регистрация: 12.03.2011
Сообщений: 21

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

17.03.2014, 18:28. Просмотров 564. Ответов 0
Метки (Все метки)

Программа должна находить большие простые числа с помощью алгоритма Лемана. Написал программу, но для большого числа, например 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 ;
//---------------------------------------------------------------------------
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru