204. Count Primes

问题：

求从0 到 小于给定n 的正整数中，有多少个素数（质数）。

素数：只能被 自己 和 1 整除。（1和0不是）

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

Constraints:
0 <= n <= 5 * 10^6

　　

解法：math （数学算法）

思路：

首先将所有数标记为true，（初始化都为素数）

从 i = 2 开始，

i：2的倍数 2，直到n，都不为素数，标记为false。

i：3的倍数 2，直到n，都不为素数，标记为false。
⚠️ 这里，3的2倍，其实已经被【2的3倍】处理过，可省略。因此，遍历倍数，只需要从 i 自己开始即可。

i：4的倍数 4， 直到n，都不为素数，标记为false。

⚠️ 这里，4的 j 倍，其实已经被【2的 2j 倍】处理过，可以省略，同理对所有合数都是这样，因此，可以只遍历到目前为止的质数。

i：5的倍数 5，直到n，都不为素数，标记为false。

......

⚠️ 一直遍历到 i*i < n 即可，

若 i*i>=n, 由于 遍历 i 的倍数 i，直到 n，那么这个可遍历的倍数已经不存在了。也就无需遍历。

最后统计true的个数，即为所求。

代码参考：

class Solution {
public:
    int countPrimes(int n) {
        //initialize all num to be prime.
        //then start from 2, 2's n times(n=2,3,4...) should not be prime, mark to false.
        //     next prime num loop do this.
        //      (cause non-prime num 's times already count in former loop)
        //     e.g. 6 (which has been marked false in 2's 3 times)
        //          6*2 = 12 = 2*3*2 = 2*6 (which has been marked false in 2's 6 times)
        if(n==0 || n==1) return 0;
        vector<bool> isPrime(n, true);
        int res = 0;
        isPrime[0] = false;
        isPrime[1] = false;
        for(int i=2; i*i<n; i++) {
            if(isPrime[i]) {
                for(int j=i*i; j<n; j+=i) {//j: i's times
                    // originally j=i*2(start from 2), but beacause of a*b==b*a
                    //  e.g. j=5*2, when we want to mark 5's 2 times.[10]
                    //              isPrime[10] has been marked at 2's 5 times.
                    // so, we just need to start with times>=i.
                    isPrime[j] = false;
                }
            }
        }
        for(bool ip:isPrime) {
            if(ip) res++;
        }
        return res;
    }
};