使用 Java Sieve of Eratosthenes 算法处理大量数据时出现奇怪的数值错误？
我遇到了最奇怪的问题，并且调试它的过程很糟糕。我想我应该将其发布在这里以征求任何意见。
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
As 直接从种子值开始“划掉”，而不是从平方开始（这是我的教授在他的示例代码中所做的），它就会起作用。
这让我只能假设当 i 非常大时，正方形会发生一些奇怪的事情。
有什么建议吗？
I'm experiencing the strangest problem and have been having a terrible time debugging it. I thought I'd post it here to get any opinions.
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;
}
}
}
}
(assume mPrimes are all initially true)
Here's the catch:
When I run this program with limits of 10, 100, 1000, 10000, and even 100000, it reports counting the correct number of primes below the given number, as cross-referenced with this page: http://primes.utm.edu/howmany.shtml
However, when I run with an argument of 1000000 (one million), I get a result that is exactly 7 away from the correct value (it reports 78491 instead of 78498).
Furthermore, All the other methods of prime-counting I've implemented in this program report the correct value.
And here's the real catch: If I replace
i*i
with
i+i
As to start "crossing out" directly from the seed value, instead of starting from the square (which is what my professor had done in his sample code), it works.
This leaves me only to assume that something strange is happening with the square when i is very large.
Any suggestions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这是一个溢出错误。 1,000,000 * 1,000,000 需要的位数超出了 int (2*32 - 1) 所能容纳的位数。您需要使用长整型 (2*64 -1)。
Its an overflow error. 1,000,000 * 1,000,000 needs more bits than an int (2*32 - 1) can accommodate. You need to use a long (2*64 -1).
如果
i*i超过限制，则交叉任何数字都是没有意义的。因此，不要使用长整数，只需将变量strike_limit初始化为sqrt(i)的上限，并且在以下情况下甚至不要尝试进入删除循环： >i 超出了该限制。 的效果抱歉，我不太了解 Java，无法在其中编写代码，但这应该是int Strike_limit = (int) (sqrt ((double)limit) + 0.5); 。
这可以保证您在计算 i² 时不会溢出。小心分析极端情况。
There is no point to cross any numbers if
i*iexceeds a limit. So instead of going long integers, just initialize a variablestrike_limitto be a ceiling ofsqrt(i), and do not even try entering the strike-out loop ifiexceeds that limit. Sorry I do not know Java well enough to write code in it, but that should be something to the effect ofint strike_limit = (int) (sqrt ((double)limit) + 0.5);
This guarantees you from overflow when calculating i². Be careful to analyze corner cases.
另外，为了避免溢出，外循环可以是这样的：
for (int i = 2; i*i < limit; i++)，而且它会更快（因为任何非素数）limit下的sqrt(limit)下必须至少有一个素数）Also, to avoid overflow, outer cycle can be like this:
for (int i = 2; i*i < limit; i++), and it will be even faster (cause any non-prime number underlimitmust have at least one prime divisor undersqrt(limit))变量 i 最初为 2，并在每一步中增加，因此它始终为正。变量j最初为i×i，为正数，并在每一步增加正数i ，因此 j 始终为正。你为什么要测试j> 0 在内循环中？
Variable i is initially 2 and increases at each step, so it is always positive. Variable j is initially i × i, which is positive, and increases by the positive number i at each step, so j is always positive. Why do you test j > 0 in the inner loop?