java - 查找从 2 到 1000 的所有素数的算法不起作用

Question

这是一段代码，使用语句计算从 2 到 1000 的所有素数，数字 n 是素数当且仅当:

在第一个版本中，我认为我正确地实现了算法:

public class Giuga {

    public static void main(String[] args){
        int n = 2;

        while(n<=1000){
            int k = 1;
            long sum = 0;
            while(k<=n-1){
                sum = sum+(long)Math.pow((double)k,(double)n-1);
                k++;
            }
            if(sum%n==n-1){
                System.out.println(n + " is a prime.");
            }
            n++;
        }
    }
}

但是，由于变量 sum 增长很快，发生溢出，素数 17 之后将不再有输出。

为了防止我必须使用这个:

好吧，我做到了，这是我的 2. 版本:

public class Giuga {

    public static void main(String[] args){
        int n = 2;

        while(n<=1000){
            int k = 1;
            long sum = 0;
            while(k<=n-1){
                sum = sum+((long)Math.pow((double)k%n,(double)n-1))%n; //Here are the changes
                k++;
            }
            if(sum%n==n-1){
                System.out.println(n + " is a prime.");
            }
            n++;
        }
    }
}

我认为我做对了，但是现在输出在素数 13 之后停止了。

一段时间以来，我一直在努力找出我的错误。我究竟做错了什么？从 2 到 1000 必须有 168 个素数。

Answer 1

正如已经指出的那样，double 的精度只有大约 16 位，不够精确，无法在计算足够大的数字时保持正确的余数。

您可以切换到 long 并执行您自己的模幂运算。

int k = 1;
long sum = 0;
while(k<=n-1){
    long pow = 1;
    for (int i = 0; i < n - 1; i++)
        pow = (pow * k) % n;
    sum = (sum + pow)%n;
    k++;
}

可以通过将这种简单的模幂运算更改为通过重复平方使用模幂运算来改进该算法，它不是最有效的素数查找算法，但现在是正确的。

2 is a prime.
3 is a prime.
5 is a prime.
7 is a prime.
11 is a prime.
13 is a prime.
17 is a prime.
19 is a prime.
23 is a prime.
29 is a prime.
31 is a prime.

(剪断)

977 is a prime.
983 is a prime.
991 is a prime.
997 is a prime.

要通过重复平方使其模幂，替换

long pow = 1;
for (int i = 0; i < n - 1; i++)
    pow = (pow * k) % n;

与

long pow = 1;
long square = k;
int exp = n - 1;
while (exp > 0)
{
    if ((exp & 1) == 1)
    {
        pow = (pow * square) % n;
    }
    square = (square * square) % n;
    exp >>= 1;
}

它连续测试指数的每一位，如果已设置，则将当前平方乘以 pow。