Почему мой тест Ферма на первичность не работает? - PullRequest
Новая
       13

Почему мой тест Ферма на первичность не работает?

0 голосов
/ 04 января 2019

Я пытаюсь реализовать метод, который проверяет любое целое число и возвращает истину, если оно простое, с помощью критерия примитивности Ферма.

Я разделил проблему в зависимости от того, является ли вход меньше 40 или нет. Если входное значение меньше 40, тогда я применяю тест для каждого целого числа вплоть до n-1. Иначе, если целое число больше 40, тогда тест применяется для каждого целого числа вплоть до 40. Однако для некоторых простых он не выполняется. 

public static boolean isPrime (double n){
    int counter=0;
    boolean isPrime=false;
    if(n<40) {
        for (int a = 2; a < n - 1; a++) {
            if (Math.pow(a, n - 1) % n == 1) counter++;
        }

        if (counter == n - 3) isPrime = true;
    }
        else {

        for (int a = 2; a <= 40; a++) {
            if (Math.pow(a, n - 1) % n == 1) counter++;

        }
        if (counter == 39) isPrime = true;
    }
    return isPrime;
}

Это логическая проблема или что-то еще?

1 Ответ

0 голосов
/ 04 января 2019

Math.pow работает на удваивается, и результат только приблизительный. Modulo, с другой стороны, работает с целыми числами, чей диапазон составляет немногим более 2 миллиардов. Может, ваш пауф производит какие-то числа больше, чем случайно? (17 ^ 18 кажется верной ставкой для 19 ...)

Так как это исправить: Вы можете реализовать свой собственный pow (a, b, n) (степень по модулю n), используя умножение и по модулю на целых числах. Это должно работать правильно. Создайте функцию для возведения a в степень b, используя последовательность умножений, примените% n к промежуточному результату после каждого шага ...

...