16 ms Java solution modified from the hint method


  • 3
    H
    public int countPrimes(int n) {
        if(n <= 2) {
            return 0;
        }
        boolean[] isPrime = new boolean[n];
        for(int i = 2;i < n;i++) {
            isPrime[i] = true;
        }
        
        int count = n / 2;//only count odd numbers
        
        
        for(int i = 3; i * i < n; i += 2) { // i += 2 counts only odd numbers
            if(!isPrime[i]) continue;
            
            for(int j = i * i;j < n;j = j + 2 * i) {
                if(isPrime[j]) { // once find a not marked non-prime number, subtract count by 1
                    count--;
                }
                isPrime[j] = false;
            }
        }
        
        return count;
    }

Log in to reply
 

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