204 Count Primes

　Description:

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

统计质数：给定一个非负整数n，统计出比n小的质数的个数。此题乍一看很简单，就是写一个函数判断是否为质数，再进行n次循环即可。但测试数据会出现非常大的n，用一般方法会运行超时。传统方法判断一个数是否为质数的时间复杂度为O(log2n)（与根号n作比较），n个数的时间复杂度再乘以n。

leetcode将此题标为简单，因为他给了一系列提示，给出了另外一种算法，用更多的内存换取时间上的缩短。整体思路是生成一个元素个数为n（n为输入）的数组（初始化为０），把从４开始到n结束所有的合数设置为１，再从２遍历数组，遇到为０的元素计数加一即可。我先把代码粘在下面，看不懂可以看leetcode的题目链接https://leetcode.com/problems/count-primes/　上面有完整的hints

class Solution {
public:
    void SetFlag(vector<int>& vec, int n, int max) {
        long long int t = n;    //转换成长长整形，否则n平方后可能会溢出
        for(long long int i = t * t; i < max; i += n) {
            vec[i] = 1;
        }
    }
    int countPrimes(int n) {
        if(n < 3) return 0;
        // int *vec = (int *)malloc(sizeof(int) * n);
        vector<int> vec(n + 1, 0);
        for(int i = 2; i < n; i++) {
            SetFlag(vec, i, n);
        }
        int count = 0;
        for(int j = 2; j < n; j++) {
            if(!vec[j]) {
                count++;
            }
        }
        return count;
    }
};