11-07 计数质数

原题链接

解析：
所谓质数，是指除了本身不能被其他数字整除的数。
如果给出的n的范围小于10^5，可以使用打表的方式进行求解：
1、首先判断这个数字是不是素数；
2、如果是素数加入数组当中去；
给出求100以内质数表相应的代码：

const int maxn = 101;
bool p[maxn] = {false};
bool is_p(int n)
{
	if(n <= 1)
		return false;
	int sqr = (int)sqrt(1.0* n);
	for(int i=2; i<=sqr; i++)
	{
		if(n % i == 0)
			return false;
	}
	return true;
}
int isprime[maxn], k=0;
int find_p(int n)
{
	for(int i=1; i<maxn; i++)
	{
		if(is_p(i) == true)
		{
			isprime[k++] = i;
			p[i] = true;
		}
	}
}

但题目给出的范围大于10^6，因此考虑埃式筛选法，时间复杂度为O(N)。
其思想在于，算法从小到大进行枚举，对每一个素数，计算其所有的倍数，剩下的便全为素数。使用一个数组p进行标记，如果数字A被筛选掉，那么p[A]=true,初始化全为false;
给出筛选法的核心代码：

for(int i=2; i<n; i++)
        {
            if(p[i] == 0)
            {
                prime.push_back(i);
                for(int j=i+i; j<n; j+=i)
                {
                    p[j] = 1;
                }
            }
        }

注意事项：
vector<>不能直接初始化，打表初始化的阶段浪费不少时间；
vector<>可以根据下标直接赋值；

给出完整代码：

class Solution {
public:
    int countPrimes(int n) {
        if(n < 3)
            return 0;
        vector<int> p;
        for(int i=0; i<n; i++)
        {
            p.push_back(0);
        }
        vector<int> prime;
        for(int i=2; i<n; i++)
        {
            if(p[i] == 0)
            {
                prime.push_back(i);
                for(int j=i+i; j<n; j+=i)
                {
                    p[j] = 1;
                }
            }
        }
        int cnt = 0;
        for(int i=0; i<prime.size(); i++)
        {
            if(prime[i] < n)
            {
                cnt++;
            }
        }
        return cnt;
    }
};

最后耗时176ms，效果也算是比较不错了！