使用篩子查找質數小於LONG的數字

-1

我必須找到小於或等於給定數字n的質數數量。我正在使用Eratosthenes的篩子來尋找素數。使用篩子查找質數小於LONG的數字

這是我寫的代碼：

static int find_prime(int n) { 
    boolean[] arr = new boolean[n+1]; 
    Arrays.fill(arr, true); 

for(int i=2;i<=n;i++) { 
    if(arr[i]==true) { 
     for(int j=2*i; j<=n; j+=i) 
      arr[j] = false; 
    } 
} 
int count=0; 
for(int i=2;i<=n;i++) { 
    //System.out.print(arr[i]+" "); 
    if (arr[i] == true) 
     count++; 
    } 
    return count; 
}

此代碼非常適用於integer價值，但我要實現它long數字。而Java不允許創建long大小數組，因此boolean[] arr = new boolean[n+1]; 不起作用。有人可以建議我一種方法來解決這個問題嗎？

來源

2016-08-11 Krishh

[Java array with 4gb elements]可能重複（http://stackoverflow.com/questions/878309/java-array-with-more-than-4gb-elements） – azurefrog

你已經購買了10 [ Exabytes]（http://www.whatsabyte.com/）爲你的篩選，對吧？ – dasblinkenlight

還有更多節省空間的方法來存儲一系列布爾值。例如，一個位域。另外，你並不需要在篩中代表偶數。 – khelwood

您將沒有足夠的內存來表示整個篩網，因爲它是以百兆字節爲單位的。即使是BitSet也不會適合您需要的所有索引，因爲最終它將存儲這些位的數組long。

你可以找到一個混合的方法你的答案：

構建和高達Integer.MAX_VALUE
收穫素數高達Integer.MAX_VALUE運行篩入的long小號
數組注意，你可以停止在達到候選號碼的平方根時檢查除數c
這意味着您已經擁有所有可能的除數，高於Integer.MAX_VALUE
使用除數的陣列Integer.MAX_VALUE和n

之間的篩選數量，因爲你不需要Integer.MAX_VALUE後儲存額外的素數，你的代碼就不會耗盡內存。

來源

2016-08-11 14:51:43 dasblinkenlight

感謝您提及BitSet不足以減少內存需求。如果我認爲這是正確的，它仍然需要多達2^60個字節的內存。我不認爲目前常見的桌面處理器可以解決這麼多問題。 –

使用篩子查找質數小於LONG的數字

回答

相關問題