Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Помогите найти ошибку в реализации теста простоты

Автор: Splendid 10.6.2008, 11:18

Помогите найти ошибку, пожалуйста!
На нечетных числах просто зависает....

Код

Автор: rrrFer 10.6.2008, 11:57

Splendid,
функция involution_on_mod не понятно что возвращает

Код

involution_on_mod (int b, int s, const m){

если я правильно понял - программа должна определять взаимную простоту 2х чисел?

Код


#include <iostream>
#include <stdlib.h>
using namespace std;
bool e(int a, int b){
    int n=a;
    if(a>b)  n=b+1;
    if(a<b)  n=a+1;
    if(a%2==0&&b%2==0)
        return 0;
    for(int i=3;i<n;i+=2)
        if(a%i==0&&b%i==0)
            return 0;
    return 1;
}
void main(){
    cout<<e(109,108)<<endl;
    system("pause");
}

Автор: Splendid 10.6.2008, 12:17

нет, программа должна проверять число на простоту

Добавлено через 47 секунд
но вычисление НОД там тоже присутствует, как часть алгоритма

Добавлено через 1 минуту и 46 секунд
вот сам алгоритм теста:

Вероятностный тест Миллера-Рабина

Пусть n — нечетное и n − 1 = 2st, t — нечетное.
Если число n является простым, то при всех a > 1 выполняется сравнение
an−1 ≡ 1 (mod n)
Поэтому, рассматривая элементы {at, a2t, …, a2s−1t} можно заметить, что либо среди них найдется равный −1 (mod n), либо at ≡ 1 (mod n).
На этом замечании основан следующий вероятностный тест простоты:
1.    выбираем случайное число a из интервала {1, 2, …, n−1} и проверяем с помощью алгоритма Евклида условие (a, n) = 1;
2.    если оно не выполняется, то ответ «n — составное»;
3.    вычисляем at (mod n);
4.    если at ≡ ±1 (mod n), то переходим к п. 1;
5.    вычисляем a2t, …, a2s−1t до тех пор, пока не появится −1;
6.    если ни одно из этих чисел не равно −1, то ответ «n — составное»;
7.    если мы достигли −1, то ответ неизвестен (и тест можно повторить еще раз).

Добавлено через 10 минут и 23 секунды
здесь и а - в степени и t в степени

Автор: rrrFer 10.6.2008, 12:42

Splendid,

Цитата(Splendid @ 10.6.2008, 12:17

)

программа должна проверять число на простоту

Код


#include <iostream>
#include <stdlib.h>
using namespace std;
bool e(int a){
    int i,n=a/2;
    for(i=2;i<n;i++)
        if(a%i==0)
            return 0;
    return 1;
}
void main(){
    cout<<e(5)<<endl;
    system("pause");
}

а насчет того алгоритма, котоый вы написали...два первых шага уже обеспечивают  вероятность неправильной работы программы в ряде случаев:
1.    выбираем случайное число a из интервала {1, 2, …, n−1} и проверяем с помощью алгоритма Евклида условие (a, n) = 1;
2.    если оно не выполняется, то ответ «n — составное»;

Автор: Splendid 10.6.2008, 13:04

а в чем неправильность?

Автор: rrrFer 10.6.2008, 13:07

Splendid,
число случайное...

Автор: Splendid 10.6.2008, 13:11

т.е. мне нужно как-то прикрутить сюда еще генератор случ.чисел?

Автор: bsa 10.6.2008, 13:48

Splendid, зачем генератор? Просто функции rand() будет достаточно (только srand на забудь вызвать в начале программы, передав текущее время в качестве параметра).

Автор: Splendid 10.6.2008, 14:23

bsa, а можно пример, никогда этой функцией не пользовалась...

Автор: rrrFer 10.6.2008, 14:30

Splendid,

Код


#include <stdlib.h>
#include <stdio.h>
#include <time.h>
void main(){
    time_t t;
    srand((unsigned) time(&t));
    int i=rand();
    printf("%d\n", i);
    system("pause");
}

если srand не вызывать, то работать будет, но числа будут одни и теже каждый раз...(т.е. генерируютсяи вроде-бы случайные, но при любом запуске программы одинаковые). Можно также использовать randomize() и random(), но не все компиляторы их поддерживают

Автор: Splendid 10.6.2008, 14:34

понятно, спасибо!
Но это дела не изменило, все равно работает не так, может Вы опытным взглядом еще какую-нить ошибку видите?

Автор: Splendid 11.6.2008, 08:50

Спасибо! с ошибками разобралась, код за ненадобностью убрала

Автор: bronislav 11.6.2008, 10:39

Splendid, ИМХО не стоило убирать код. Возможно кто-то тоже встретиться с этой проблемой.