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

Затруднения в реализации теста Ферма - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ помогита пожалуйста дело горит http://www.cyberforum.ru/cpp-beginners/thread7512.html
Извеняюсь заранее за свой русский =) помогите и меня тупик :help: я делаю екзаменацеоную работу -игру 2D на с++ в виндоусе и столкнулся с проблемой !!:eek: у меня масив должен запустить ресунок я сделал ро родобию как на кнопке только вместо условия нажатия поставил условие и не работает как мне ето зделать помогите плизз :'(
C++ Вычислить минимальный по модулю элемент массива Помогите решить задачу! Наработки есть, но... В одномерном массиве, состоящем из n целых элементом, вычислить: 1. Минимальный по модулю элемент массива; 2. Сумму модулей элементов массива, расположенных после первого элемента, равного нулю. Преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоящие в чётных позициях, а во второй половине – элементы,... http://www.cyberforum.ru/cpp-beginners/thread7500.html
C++ Алгоритм поиска строк в текстовом файле
Доброго времени суток! Есть текстовый файл размером ~65 Мб, ~605000 строк. Из этих строк необходимо выделить строки, котрые содержат подстроки "10077" и "Новая запись:" и сохранить их в другой текстовый файл. Написал следующий код: #include <stdio.h> #include <string.h> int main(void) { FILE* log_file; FILE* result_file;
C++ Помощь при работе с функциями в Си++
Как правильно обратится к элементам массива в функции zam int zam(int n, int m, int**a) { int tmp; for(int i=0; i<n; i++) for(int j=0; j<m; j++) a=tmp; a=a; a=tmp; return tmp;}
C++ Вычислить значение выражения http://www.cyberforum.ru/cpp-beginners/thread7450.html
Помогите пожалуйста доделать программу. #include<iostream> #include<math.h> #include<fstream> #include <conio.h> double a=16,b=0.54,c=5,u1=5,u2=65; float uin,uout,t,dt,uid=0,uod=0; int i=0; using namespace std;
C++ Игра Сапер Я студент 2 го курса на курсовую дали игру сапер. Нужно связать правую кнопку мыши в ClassWizard для того чтобы ставить флажки на мины. Заранее спасибо. Ну если подкинете идеи для решения всей задачи буду очень признателен. подробнее

Показать сообщение отдельно
Phoenix777
Сообщений: n/a
20.04.2008, 13:48     Затруднения в реализации теста Ферма
В книге Смарта был дан следующий алгоритм для реализации теста Ферма на псевдокоде (число является псевдопростым, если a^N-1=mod(n) - может быть и составным с нкоторой вероятностью и 100% составным в противном случае):

Код
for (i=0; i<k; i++)
{
выбрать a из [2,...,n-1];
b=a^(n-1)modn;
{напечатать (составное, a)
exit;
}
}
напечатать правдоподобно простое

Вот моя реализация на C++:
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

int main()
{
int n; //проверяемое число  
int i; //счетчик циклов
int k; //количество циклов
int a; //основание
int b;
cout << "Test Ferma" << endl << "Enter number: ";
cin >>n;
cout << "Kolichestvo tsiklov: ";
cin >>k;
bool sim_prime; 
sim_prime=true; //предположение, что число n правдоподобно простое  
int rand_2toN(int n);
for (i=0; i<k; i++) //проверка на простоту
{
a=rand_2toN(n)+1;  // выбор случайного основания от 2 до n-1
b=(static_cast<int>(pow(a, n-1)))%n;     
if (b!=1)
{
sim_prime=false;
break;
}
}
if (sim_prime)
cout << "Chislo pravdopodobno prostoe";
else
cout << "Chislo sostavnoe " << a << " - svidetel'";
cin.get();
cin.get();
return 0;
}
int rand_2toN(int n)
{
return rand() %n-3;   
}
Методом проб понял, что проблема заключается в вычислении цикла - значение a^N-1(modn) ((static_cast<int>(pow(a, n-1)))%n) вычисляется неверно - получаются различные числа, отличные от единицы для простых чисел, а согласно Ферма a^N-1=1(modn). Не могу найти причину, пожалуйста подскажите, если знаете, спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 07:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru