查找从2到1000的所有素数不起作用的算法 [英] Algorithm to find all primes from 2 to 1000 not working

问题描述

这是使用该语句计算从2到1000的所有素数的一段代码，数字n是素数iff：

Here's a piece of code to compute all primes from 2 to 1000 using the statement, that a number n is a prime number iff:

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

In the first version I think that I implemented the algorithm correctly:

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++;
        }
    }
}

但是，因为变量总和快速增长，发生溢出，在素数17之后将不再有输出。

But, since the variable sum grows rapidly, an overflow happens and after the prime number 17 there will be no output anymore.

为了防止这种情况发生我必须使用这个：

To prevent that I have to use this:

< img src =https://i.stack.imgur.com/lAlMl.pngalt =在此处输入图像说明>

嗯，我这样做了，这是我的2.版本：

Well, I did that and here is my 2. version:

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之后停止。

I think I did it correctly, but now the output stops after the prime number 13.

我试图找出我的错误已经有一段时间了。我究竟做错了什么？
从2到1000必须有168个素数。

I'm trying to find my mistake for quite some time now. What am I doing wrong? There must be 168 primes from 2 to 1000.

推荐答案

正如已经指出的那样， double s，只有大约16位精度，不够精确，不足以维持正确的余数，以便在足够高的数字上进行计算。

As has been pointed out, doubles, which only have about 16 digits of precision, aren't precise enough to maintain the correct remainders for calculations on high enough numbers.

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

You can switch to longs and perform you own modular exponentiation.

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++;
}

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

This algorithm could be improved by changing this straightforward modular exponentiation to using modular exponentiation by repeated squaring, and it's not the most efficient prime finding algorithm, but it is now correct.

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.

要通过重复平方进行模幂运算，请替换

To make it modular exponentiation by repeated squaring, replace

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

with

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 如果已设置。

It tests each bit of the exponent in succession, and multiplies the current square in to pow if it's set.

这篇关于查找从2到1000的所有素数不起作用的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！