java - 算法:使用 Eratosthenes 筛法列出所有质数

Question

我已经实现了 Eratosthenes 筛法 来查找从 1 到 n 的素数列表。我的代码对于从 1 到 10,000 的输入工作正常，但我得到的值 >100,000:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2146737495
        at SieveOfEratosthenes.main(SieveOfEratosthenes.java:53)

我能够找到问题，这是在我执行 i * i 时出现在 for 循环中，因为它超出了整数范围 (Integer.MAX_VALUE ), 但我找不到解决方案。有人可以建议我可以做哪些更改吗？如果有人建议我提高此实现的效率，我也很感激？

public class SieveOfEratosthenes {

    public static void main(String[] args) {

        Integer num = Integer.parseInt(args[0]);
        Node[] nodes = new Node[num + 1];

        for(int i = 1; i < nodes.length; i++) {

            Node n = new Node();
            n.setValue(i);
            n.setMarker(true);

            nodes[i] = n;
        }

        for(int i = 1; i < nodes.length; i++) {

            if(nodes[i].getMarker() && nodes[i].getValue() > 1) {
                System.out.println("Prime " + nodes[i].getValue());
            } else {
                continue;
            }

            for(int j = i * i; j < nodes.length
                                    && nodes[i].getMarker(); j = j + i) {
                nodes[j].setMarker(false);
            }
        }

        System.out.println(l.size());

    }
}

class Node {

    private int value;
    private boolean marker;

    public void setValue(int value) {
        this.value = value;
    }

    public int getValue() {
        return this.value;
    }

    public void setMarker(boolean marker) {
        this.marker = marker;
    }

    public boolean getMarker() {
        return this.marker;
    }

    public String toString() {
        return ("Value : " + marker + " value " + value);
    }
}

Answer 1

本质上，for(int j = i * i; ...循环是划掉i的所有倍数.只有从 i * i 开始划掉才有意义，因为所有较小的倍数都已经被它们的较小的除数划掉了。

从这里至少有两种方法。

首先，你可以从i * 2开始划掉而不是 i * i .这将摆脱溢出。不利的一面是，筛的复杂度将从 O(n log log n) 增加到 O(n log n)。

其次，您可以检查是否i * i已经太多了，如果是，则完全跳过循环。回想一下，对于 i，它基本上被跳过了。大于 nodes.length 的平方根如果没有发生溢出。例如，只需添加一个 if (i * 1L * i < nodes.length)在循环之前。