アルゴリズム：EratosthenesのSieveを使ってすべての素数を列挙してください

Question

Sieve of Eratosthenesを実装して、1からnまでの素数のリストを見つけました。私のコードは、10,000 1からの入力のために正常に動作しているが、私は値> 10万以下取得しています：

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

私はそれがあるように私はi * iをやっている時にループのためにある問題を、見つけることができています整数の範囲（Integer.MAX_VALUE）から出ていますが、解決策を見つけることができませんでした。誰かが私にこの変更を効率化するための改良を提案してくれれば、何ができますか？

int limit = 2 << 14; 
for(int i = 1; i < nodes.length; i++) { 
    if(nodes[i].getMarker() && nodes[i].getValue() > 1 && i <= 2 << 15) { 
     System.out.println("Prime " + nodes[i].getValue()); 
     if (i > limit) { 
      continue; 
     } 
    } else { 
     continue; 
    } 

Answer 1

TO

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 2

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; ...ループがiのすべての倍数を消しすることです。 i * iから始まるクロスアウトは意味がありません。これは、より小さい倍数はすべて、より小さい除数によって既に除外されているからです。

ここからは少なくとも2つの方法があります。

最初に、i * iの代わりにi * 2からクロスアウトを開始できます。 これはオーバーフローを取り除きます。 悪い面では、ふるいの複雑さはO（n log n）からO（n log n）に増加します。

第2に、すでにi * iが過剰に存在するかどうかを確認し、そうである場合は完全にループをスキップします。 iは、オーバーフローが発生しなければ、本来はの平方根より大きくスキップされます。 たとえば、ループの前にif (i * 1L * i < nodes.length)を追加するだけです。