时间戳

首页 > 解决方案 > 为什么我的费马素数检验方法不起作用？

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

问题描述

我正在尝试实现一种检查任何整数的方法，如果它是使用费马素数测试的素数，则返回 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;
}

这是逻辑问题还是其他问题？

标签： javaprimes

解决方案

Math.pow 适用于双精度数，结果只是近似值。另一方面，模数适用于范围高达 20 亿多一点的整数，你的 pow 是否会产生一些比这更大的数字？（17^18 似乎是 19 的可靠赌注……）

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

推荐阅读