Java：Eratosthenes的篩子：數組作爲參數

我的目標是關閉或設置爲false，所有不是素數的數組點。數組作爲參數提供。Java：Eratosthenes的篩子：數組作爲參數

public static boolean[] sieveOfEratosthenes(boolean [] a){ 

    int increment= 2; 

    for(int n = 0; n < 9; n++){ 
     for(int i = increment; i < a.length; i += increment){ 
      a[i] = false; 
     } 
     increment += 1; 
    } 
    a[2] = true; 
    a[3] = true; 
    a[5] = true; 
    a[7] = true; 
    return a; 
}

代碼工作正常，我只是想知道如果有一個更有效的方法比使用：

a[2] = true; 
a[3] = true; 
a[5] = true; 
a[7] = true;

重置這些數組項爲真。

在此先感謝！

來源

2012-08-31 user1172534

顧名思義，所有不是'false'的點應該是'true'，對嗎？因此，將整個數組初始化爲「true」，然後設置不能爲「false」的素數的位置。 –

這是一項家庭作業，我無法改變這個數組，他們都被設置爲true。我假設提供的數組充滿了從0- * infinity * – user1172534

@HunterMcMillen數字的數組不會是更少的操作，只需在初始化爲false後將true設置爲true？更多的素數比不素數。 –

一個好辦法做到這一點是在迭代開始你的循環* 2。所以你的循環看起來像這樣

int increment= 2; 

for(int n = 0; n < 9; n++){ 
    for(int i = increment*2; i < a.length; i += increment){ 
     a[i] = false; 
    } 
    increment += 1; 
}

這樣你跳過第一個。

第二次修改外部循環，以便它忽略由於其主要因素處理其產品而已經爲假的值。現在你的循環看起來像這樣

int increment= 2; 

for(int n = 0; n < 9; n++){ 
    if(a[increment]) { 
     for(int i = increment*2; i < a.length; i += increment){ 
      a[i] = false; 
     } 
     increment += 1; 
    } 
}

三來處理在你的陣列任何規模大小數組循環爲您增值

int count = a.length; 

for(int increment = 2; increment < count; increment++){ 
    if(a[increment]) { 
     for(int i = increment*2; i < count; i += increment){ 
      a[i] = false; 
     }   
    } 
}

該電流回路採用1和0被認爲是黃金。因此設置a[0] = a[1] = false;以反映0和1不是素數的事實。

來源

2012-08-31 21:42:51 Ge3ng

優秀的答案！謝謝！ – user1172534

做一個更好的方法是在int i = increment * increment'開始你的循環，並且對於所有* odd *增量增加'i + = 2 * increment'。然後將最後一個循環的停止條件改爲'for（...; increment <= count/increment; ...）'。我認爲你在結尾的句子中有一個錯字（缺少*「不是」*）。爲你修復它！ :) –

Java：Eratosthenes的篩子：數組作爲參數

回答

相關問題