JAVA 9ms version


  • 1
    Y
    public int countPrimes(int n) {
        if (n < 3) return 0;
        int primeNum = n / 2; // Count all the odd number
        boolean[] isPrime = new boolean[n];
        int sqrtN = (int) Math.sqrt(n);
        for (int i = 3; i <= sqrtN; i += 2) {
            if (!isPrime[i]) {
                for (int j = i * i; j < n; j += i * 2) {
                    primeNum -= (isPrime[j])? 0: 1;
                    isPrime[j] = true;
                }
            }
        }
        return primeNum;  
    }

Log in to reply
 

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