1

我的 Eratosthenes 筛遇到了问题。我想写一个筛子，它不需要所有数字的数组，直到你想要的最大素数，而只是在筛子到达它时跟踪每个素数倍数。这意味着您不必预先完成所有工作，而可以在需要时确定下一个素数。添加诸如“从 N 开始查找 K 个素数”之类的界面功能也很容易。这是伪代码：

Begin with current number set to 2
Loop:
    If prime queue is not empty:
        Peek at the top prime in the queue
        If current > top, we can move top to the next multiple
            Remove the top prime from the prime queue
            Increment top to its next multiple
            Re-add it to the queue
        If current == top, current is not a prime
            Increment current number to next integer
        If current < top, we've found a prime
            Break
Push current number onto prime queue
Increment current number to next integer
Return the new prime

所以问题来了：我正确计算了前 31 个素数（最多 127 个），但之后它认为每个数字都是素数。我已经把我的代码放在了 Ideone 上——我希望它是一些 Java 集合行为，或者一个微不足道的错误，而不是算法本身。我想不出算法应该在一定数量的素数后中断的原因。我已经手动确认在 127 之后，如果堆的排序正确，我的算法应该将 128 识别为不是素数，但这不是代码向我显示的。

有什么建议么？

http://ideone.com/E07Te

（当然，一旦我得到基本算法的工作，我会增加 2（以跳过所有非素数偶数）。我可能还会使 Sieve 成为可迭代的。）

4

2 回答 2

4

你的问题是

top.multiple == current

与

Integer current = 2;
Integer multiple;

如果我没记错的话，有一个绝对值小的 s 缓存，所以比较使用的比较Integer相同的实例的值小于 128。但是从 128 开始，你得到一个新的装箱的对象，这是一个不同的对象引用的那个。-128127==Integercurrenttop.multiple

比较使用equals或声明int current;来解决它。

并改进你的算法，只注意素数平方的每个素数的倍数。

于 2012-04-02T20:46:05.563 回答
1

您没有检查整个列表：

31 后筛堆：[[127:127], [11:132], [2:128]

您到达 132，即 > 128，因此break;在您检查 2*64 之前点击 。

于 2012-04-02T20:14:14.400 回答