算法：使用Eratosthenes篩選列出所有質數

我已實施Sieve of Eratosthenes以查找質數從1到n的列表。我的代碼工作正常進行輸入從1到10000，但我得到以下的值> 100000：算法：使用Eratosthenes篩選列出所有質數

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

我能找到的問題，這是在for循環，當我做i * i，因爲它是走出整數範圍（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); 
    } 
}

來源

2017-03-13 Vishrant

我也試過'Math.abs（j） Vishrant

@ScaryWombat我已經試過這個，並且我知道數組不能被訪問使用長期價值。它在Java文檔 – Vishrant

http://stackoverflow.com/questions/30805300/accessing-an-array-element-if-using-long-datatype-in-java這將幫助你 – Vishrant

從本質上講，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)即可。

來源

2017-03-13 02:33:00 Gassa

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

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

來源

2017-03-13 02:20:46 fxleyu

算法：使用Eratosthenes篩選列出所有質數

回答

相關問題