clear all the multiples of a index in a bitset in Java?

Question

I have a bitSet and I want to turn off all the multiples of a given index. eg: given a bitset -- > {1, 2, 3, 5, 7, 9, 11, 13, 15, 17}, I want to iterate through the bitset and turn off the multiples of each of them. In the end, I should have {1,2,3,5,7,11,13,17} which are nothing but prime numbers. so far I have:

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   
    }

need a little help here, I should be able to pick up from there..

Answer 1

you could do some thing like this:

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

or you can look at the next turned bit and turn off all its multiples:

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

here, the nextsetBit would give you the next turned on bit at or after a specified index. you increment, every position, by a factor of bit index, so that all its turned off. In each while loop, you are turning off the multiples of bit index. this is nothing but sieve logic, more details you can find in wiki.

Answer 2

Port the sieve of "Sieve of Eratosthenes" algorithm to your structure (BitSet).

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Should be straightforward enough.

Here is a Java implementation using an array. Just port it to BitSet.

http://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html