C++学习记录算法篇 埃氏筛质数

埃氏筛质数法原理：质数的倍数都不是质数，因此将质数的倍数都筛除，剩下的都是质数。

示例：

假设要筛选从1到a(a>=2)内的所有质数：

1.先设所有数均为质数(利用布尔)

2.将1设为不是质数

3.从2开始，2的倍数均不是质数；再从3开始，3的倍数均不是质数

4.此时遇到4，4在筛除2的倍数时已经被筛除，则跳过4，从5开始，以此类推筛除所有非质数

5.3，4流程重复至根号内a即可

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//以a=100为例
bool is_prime[101];

for(int i=1;i<=100;i++)
{
    is_prime[i]=true;
}//先假设所有的数都是质数

is_prime[1]=false;//1不是质数

//开始筛选
for(int i=2;i<=pow(100,0.5);i++)
{
    if(is_prime[i]==true)
    {
        for(int j=2;j*i<=100;j++)
        {
            is_prime[j*i]==false;//倍数表示方式
        }
    }//从2开始，2的倍数均不是质数
}//完成筛选