204. 计数质数 (opens new window)

方法一：数学

class Solution {
    public int countPrimes(int n) {
        int cnt = 0;
        for(int i=2;i<n;i++){
            if(isPrime(i))
                cnt++;
        }
        return cnt;
    }
    boolean isPrime(int num){
        int max = (int) Math.sqrt(num);
        for(int i=2;i<=max;i++){
            if(num%i==0)
                return false;
        }
        return true;
    }
}