204. Count Primes

problem description

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.

algorithm thought

直接求一个数是不是质数需要O(lgn)时间，遍历查看是否有两数相乘能得到n。这里是求n数中所有的质数，可以从反方向来考虑。得到一个质数之后，直接排除所有他的倍数。排除一个数只要一次计算，但是之后再来计算这个数是不是质数却需要O(lgn)时间。

可以知道，所有偶数肯定不是质数。直接从3开始计算，排除所有3的倍数。注意要从33开始，也就是9开始，而不是3或者是32=6开始。因为6已经在从2开始计算中计算过了。再比如计算5的倍数，不需要计算53=15，因为之前计算3的时候计算过35=15了。

计算3的倍数，首先是9，然后是12，然后是15以此类推，都不是质数，可以排除。但是，这里好像还是有重复计算，12 ， 18 等等数字明显都是偶数，可以直接不计算。于是修改计算倍数的代码，9直接加上23，43。

将所有质数加起来。描述的应该不是很清楚，可以仔细看看代码

code

class Solution {
public:
    int countPrimes(int n) {
        if(n<=2)
            return 0;
        vector<bool> dp(n,false);
        int half=sqrt(n);
        int res=1;
        for(int i=3;i<n;i+=2){
            if(dp[i])
                continue;
            res++;
            if(i>half)
                continue;
            for(int j=i*i;j<n;j+=2*i){
                dp[j]=true;
            }
        }
        return res;
    }
};

algorithm analysis

这里空间复杂度是O(n)，时间复杂度我也不是很会分析，看题目的hint里，分析的时间复杂度是O(n log log n).