My ac Java solution using BitSet, 254ms, can it be faster?


  • 0
    H
    public class Solution {
        public int countPrimes(int n) {
            if (n <= 2) return 0;
            BitSet bs = new BitSet(n);
            bs.set(0);
            bs.set(1);
            // skip 2, and all even numbers afterwards
            int ind = 3, count = 1, sqrt = (int) Math.sqrt(Integer.MAX_VALUE);
            while (ind < n) {
                ind = bs.nextClearBit(ind);
                // skip even numbers
                while ((ind & 1) == 0) {
                    ind = bs.nextClearBit(++ind);
                }
                if (ind >= n) {
                    break;
                }
                count++;
                // avoid overflow problem
                if (ind >= sqrt) {
                    ind += 2;
                    continue;
                }
                // ind must be odd, so we make step an even number, so that every time, i is an odd number
                for (int i = ind * ind, step = ind * 2; i < n; i += step) {
                    bs.set(i);
                }
                ind += 2;
            }
            return count;
        }
    }

Log in to reply
 

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