bitmap solution, might save some memory


  • 0

    using a bit to indicate a number. More efficient on memory.

    public class Solution {
        public int countPrimes(int n) {
            if(n <= 2) {return 0;}
            // bits, bit 0 -- is prime, bit 1 -- is not prime
            int[] bits = new int[n / 32 + 1];
            for(int i = 2; i <= Math.sqrt(n); i++) {
                if(!isSet(bits, i)) {
                    for(int j = i * i; j <= n; j +=i) {
                        setBit(bits, j);
                    }
                }
            }
    
            int count = 0;
            for(int i = 2; i < n; i++) {
                if(!isSet(bits, i)) {
                    count++;
                }
            }
            return count;
        }
        
        public void setBit(int[] bits, int index) {
            int i = index / 32;
            bits[i] |= (1 << (index % 32));
        }
        
        public boolean isSet(int[] bits, int index) {
            int i = index / 32;
            return (bits[i] & (1 << (index % 32))) != 0 ? true : false;
        }
    }
    

Log in to reply
 

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