这是一段代码,使用该语句计算所有素数从2到1000,数字n是素数iff：
在第一个版本中,我认为我正确地实现了算法：
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之后,将不再有输出.
为了防止我不得不使用这个：
嗯,我做到了,这里是我的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之后停止.
现在我试图找到我的错误了一段时间.我究竟做错了什么？
必须有168个素数从2到1000.
解决方法
如已经指出的那样,只有大约16位精度的双精度不够精确,不足以维持足够数量的计算的正确余数.
您可以切换到longs并执行您自己的模幂运算.
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.
