我遇到了最奇怪的问题,并且调试它的时间很糟糕。我想我会把它张贴在这里以征求任何意见。
public static void sieve(int limit) {
for (int i = 2; i < limit; i ++) {
if (mPrimes[i] == true) {
for (int j = i*i; ((j < limit) && (j > 0)); j += i) {
mPrimes[j] = false;
}
}
}
}
(假设 mPrimes 最初都为真)
关键是:
当我以 10、100、1000、10000 甚至 100000 的限制运行此程序时,它会报告计算出低于给定数量的正确素数,如本页交叉引用:http://primes.utm.edu/howmany.shtml
但是,当我使用 1000000(一百万)参数运行时,我得到的结果与正确值正好相差 7(它报告 78491 而不是 78498)。
此外,我在此程序中实现的所有其他素数计数方法都报告了正确的值。
真正的问题是:如果我更换
i*i
与
i+i
至于直接从种子值开始“划掉”,而不是从正方形开始(这是我的教授在他的示例代码中所做的),它是有效的。
这让我只能假设当 i 非常大时正方形发生了一些奇怪的事情。
有什么建议吗?
最佳答案
这是一个溢出错误。 1,000,000 * 1,000,000 需要的位数超过 int (2*32 - 1) 所能容纳的位数。您需要使用长 (2*64 -1)。
关于java - 使用 Java Sieve of Eratosthenes 算法大数时出现奇怪的数值错误?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9043376/