question

Count the number of prime numbers less than a non-negative number, n.

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

题解：

最直观的当然是暴力解法,直接双重for循环，把每个小于n的质数都枚举出来。但如果不做优化，代码肯定运行超时。所以我们来考虑如何尽量减少for循环的迭代次数。

• 首先，>2的偶数m肯定有因子2和m/2，即>2的偶数肯定不是质数（减少筛选的次数）
• 其次，在判断一个整数m是否是质数，也需要用for循环去迭代。这时，我们考虑以m的算术平方根分界。假设m=a*b,如果当a<=sqrt(m),a只能取得1,相应的b也只能取m，此时m为质数。
• 最后，一些小细节——判断一个质数是否为质数，可以用isPrime进行标记;题目是<n，不是<=

代码

优化过后的暴力解法

class Solution {
    public boolean isPrime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    public int countPrimes(int n) {
        int numberCount = 0;
        if (n < 3)
            return 0;
        numberCount++;
        for (int i = 3; i < n; i += 2) {
            if (isPrime(i))
                numberCount++;
        }
        return numberCount;
    }
}

另一种思路

假设现在输入的n值为10(利用空间换时间，ps:我们不需要去考虑arr[0]、arr[1]的值)

class Solution {
    public int countPrimes(int n) {
        //创建一个布尔类型的数组，如果索引值对应的值是true则为质数，反之不是质数
        boolean[] arr = new boolean[n];
        Arrays.fill(arr,true); //填充数据
        int count = 0;
        for( int i = 2; i*i<n;i++) {
            if(arr[i]) {
                //如果j为i的倍数，则j肯定不是质数
                for(int j=i*2;j<n;j+=i){
                    arr[j] = false;
                }
            }
        }
        for(int i = 2;i<n;i++) {
            if(arr[i]) {
                count++;
            }
        }
        return count;
    }
};