Accepted Java code with BitSet


  • 10
    B

    BitSet should be one of the choices in Java.

    public int countPrimes(int n) {
        BitSet bs = new BitSet(n);
        bs.set(0); bs.set(1);
        int ind = 0, count = 0;
        while(ind < n){
            ind = bs.nextClearBit(ind + 1);
            if(ind >= n)
                return count;
            count++;
            for(int i = 2 * ind; i < n; i += ind)
                bs.set(i);
        }
        return count;
    }

  • 4
    K

    Thank you! I had no idea that BitSet existed. Thanks to your idea of using BitSet, I had a very similar solution:

    public int countPrimes(int n) {
        if (n <= 1) {
            return 0;
        }
        
        BitSet set = new BitSet(n);
        set.set(0, 2);
        
        for (int i = 2; i < n; i++) {
            if (!set.get(i)) {
                for (int j = i*2; j < n; j+=i) {
                    set.set(j);
                }    
            }
            
        }
        
        return n-set.cardinality();
    }

  • 0
    B

    Good answer! I used a boolean array but using a bitset will definitely save more memory.


  • 0
    X

    Actually you do not need to count ind to n, just count to sqrt(n) and the left unset bits are all primes.


  • 0
    B

    Yes, thanks for the reminder.


  • 0
    0

    No,this program hava to count ind to n.
    You can see my optimization to your program:

            for(long i = (long)ind* (long)ind; i < n; i += ind)
                bs.set((int)i);

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.