清除Java中bitset中所有索引的倍數？

我有一個bitSet，我想關閉給定索引的所有倍數。例如：給出bitset -- > {1, 2, 3, 5, 7, 9, 11, 13, 15, 17}，我想要iterate到bitset並關閉它們中的每一個的倍數。最後，我應該有{1,2,3,5,7,11,13,17}這些只是素數。到目前爲止，我有：清除Java中bitset中所有索引的倍數？

public static void getPrimeNumbers(int n) { 
    BitSet s = new BitSet(); 
    // s.set(0); 
    s.set(1); 
    s.set(2); 
    //create the set having all numbers till n 
    for (int i = 3; i <= n; i += 2) { 
     s.set(i); 
    } 
      //for element in Bitset .... 
    //need to clear multiple of bits in iteration 
    }

這裏需要一點幫助，我應該能夠從那裏拿起..

來源

2013-12-11 eagertoLearn

您可以使用while循環或for循環，並檢查是否（s.get（i））'，然後執行s.clear（）'。 –

除了'1'不是素數，其他所有數字都是'1'的倍數。 – starblue

http://stackoverflow.com/a/1043247/49246 – starblue

你可以做一些這樣的事：

//you start from 3 because 1 and 2 are prime already 
int i = 3; 
//you can do square check, since you would have turned off all bits before you reach n 
while (i * i < n) { 
     if (s.get(i)) { 
      int k = 3 * i; 
      while (k <= n) { 
       s.clear(k); 
       k += i; 
      } 
     } 
     i++; 
    }

，或者你可以先看下翻位，並關閉所有的倍數：

for (int j = s.nextSetBit(3);j>=0;j=s.nextSetBit(j+1)){ 
      int k =3 * j; 
      while (k <= n){ 
       s.clear(k); 
       k+=j; 
      } 
     }

在這裏， nextsetBit會給你在指定索引處或之後的下一個打開的位。你增加，每個位置，一個位索引的因素，以便它的所有關閉。在每個while loop中，您將關閉位數索引的倍數。這只不過是sieve邏輯，你可以在wiki中找到更多的細節。

來源

2013-12-11 23:15:56

太棒了！這工作.. – eagertoLearn