161-用厄拉多塞筛法求质数个数

柔情只为你懂 2022-10-24 13:25 144阅读 0赞

## 厄拉多塞筛法 ##

西元前250年，希腊数学家厄拉多塞想到了一个非常美妙的质数筛法，减少了逐一检查每个数的的步骤，可以比较简单的从一大堆数字之中，筛选出质数来，这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。

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

#include<iostream>
    #include<vector>
    using namespace std;
    int countPrimes(int n)
    {
        
        vector<int> flag(n, true);//开辟n个空间，均初始化为true
        int count = 0;//定义计数器，初始化为0
        for (int i = 2; i * i < n; ++i)//1不是质数，从2开始判断
        {
        
            if (flag[i])//为true，进入if语句，即为质数，进入if语句
            {
        
                for (int j = i * i; j < n; j += i)
                //把i*i及可以整除i的数置为false，即不是质数
                {
        
                    flag[j] = false;
                }
            }
        }
        for (int i = 2; i < n; ++i)//此时是true的就是质数了
        {
        
            if (flag[i])//是质数
                count++;
        }
        return count;
    }
    
    int main()
    {
        
    	cout<<countPrimes(10)<<endl;
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][2021012921135583.png_pic_center]  
**备注：**  
1不是质数。质数又称素数。一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数；否则称为合数。质数的定义中明确指出了一个前提条件，一个大于1的自然数。1不属于这个范围，所以1不是质数。

[2021012921135583.png_pic_center]: /images/20221024/94fbb54a16304809b24cdaa7e7ff4e10.png