Algorithmus: Liste alle Primzahl mit Sieb von Eratosthenes

Question

Ich habe Sieve of Eratosthenes zum Auffinden der Liste der Primzahl von 1 bis n implementiert. Mein Code funktioniert gut für Eingänge von 1 bis 10.000, aber ich bin immer für Werte folgend> 100.000:

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

Ich bin in der Lage, das Problem zu finden, die in dem for-Schleife ist, wenn ich i * i tue, wie es ist gehen aus dem Integer-Bereich (Integer.MAX_VALUE), aber ich konnte die Lösung nicht finden. Kann mir jemand vorschlagen, welche Änderungen vorgenommen werden können? Ich schätze es auch, wenn mir jemand eine Verbesserung der Effizienz bei dieser Implementierung vorschlägt?

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

Im Wesentlichen ist die for(int j = i * i; ... Loop alle Vielfache von i ausstreichen. Es ist sinnvoll, nur ausgehend von i * i zu streichen, da alle kleineren Vielfachen bereits durch ihre kleineren Teiler durchgestrichen sind.

Es gibt mindestens zwei Möglichkeiten, von hier aus zu gehen.

Zuerst können Sie von i * 2 anstelle von i * i starten. Dies wird den Überlauf beseitigen. Auf der schlechten Seite würde die Komplexität des Siebes von O (n log log n) zu O (n log n) wachsen.

Zweitens können Sie überprüfen, ob i * i bereits zu viel ist, und wenn ja, überspringen Sie die Schleife vollständig. Erinnern Sie sich, dass es im Grunde für i sowieso übersprungen wird größer als die Quadratwurzel von nodes.length, wenn kein Überlauf auftritt. Fügen Sie beispielsweise einfach einen if (i * 1L * i < nodes.length) vor der Schleife hinzu.

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; 
     } 

TO

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; 
    }