为什么我的费马素数检验方法不起作用？

Question

我正在尝试实现一种方法，该方法使用费马素数检验检查任何整数并返回true，如果它是素数。

我根据输入是否小于 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;
}

这是一个逻辑问题还是别的什么？

Answer 1

Math.pow 适用于双打，结果只是近似值。另一方面，Modulo 适用于范围高达 20 亿多一点的整数，您的 pow 是否会产生比这更大的数字？（17^18 似乎是 19 的确定赌注...

那么如何解决这个问题：您可以使用整数上的乘法和模来实现自己的 pow（a，b，n）（幂模 n）。这应该可以正常工作。创建一个函数，使用一系列乘法将 a 提高到 b 的幂，在每个步骤之后将 %n 应用于中间结果......