使用大数目Eratosthenes算法的Java Sieve时出现奇怪的数值误差？

Question

我遇到了最奇怪的问题,并且一直在调试它.我以为我会在这里发布以获得任何意见.

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

至于从种子价值直接开始"划掉",而不是从广场开始(这是我教授在他的示例代码中所做的),它起作用.

这让我只能假设当我非常大的时候广场上发生了一些奇怪的事情.

有什么建议？

Answer 1

它出现溢出错误.1,000,000*1,000,000需要比int(2*32-1)更多的位.你需要使用长(2*64 -1).