leetcode 204. Count Primes 计算质数的数目

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

Example:

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

常规方法很容易超时，要使用高效的算法，这是google得到的

厄拉多塞筛法(Sieve of Eeatosthese)。

具体操作：先将 2~n 的各个数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于 n 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 n 的素数。

class Solution {
public:
    int countPrimes(int n) {
        
    int count=0;
    
    if(n==0) return 0;//初始化布尔数组
    bool b[n]={0};
        
        //如果不是之前质数的倍数，则count++，标记其所有倍数
    for(int t=2;t<n;t++){                   	
        if(!b[t]) {count++;
                   for(int i=t;i<n;i+=t){
                       b[i]=true;
                   }
                  }
        
    }
        return count;
    }
        
};