11-07 计数质数

旧城等待， 2022-12-19 11:50 112阅读 0赞

[原题链接][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTg4NTIzMg_size_16_color_FFFFFF_t_70_pic_center]  
**解析：**  
所谓质数，是指除了本身不能被其他数字整除的数。  
**如果给出的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，效果也算是比较不错了！

[Link 1]: https://leetcode-cn.com/problems/count-primes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTg4NTIzMg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/8dac68d656bc49618182b74a677e8a08.png