Eratosthenes素数筛

今天我们要学习素数筛，可以快速筛选出素数。
讲解之前，别忘了收藏我的编程专题哦
筛法理念

将合数从一堆数里面筛出，只留下质数。

筛选过程

先创建一个“数堆”，开多大自己定（一定记住设为全局变量，因为后面我们要写函数）。
尽量把数组开大一点，这是一个好习惯。

bool num[10005]

然后写一个函数，将“数堆”初始化为（假设全是素数）。
初始化从2开始，因为1不是素数哦。

void Eratosthenes(){
    for(int i=2;i<=10000;i++){
        num[i]=true;
    }
}

筛掉除了2这个素数的所有偶数

for(int i=4;i<=10000;i+=2){
    num[i]=false;
}

如果是3，5，7……的倍数，也要筛掉
下面的第一个循环是枚举质数。但例如9，它不是质数，它的倍数已经被算在3的倍数里了，何必去浪费这个时间呢？这就是的作用。由于i是个质数，所以j从i的第一个倍数（）开始筛出合数。

for(int i = 3;i <= N;i+=2){ 
    if(num[i] == true){
        for(int j= 2*i ;j <= N;j += i){
            num[j] = false;
        }
    }
}

示例代码

bool num[10005]
void Eratosthenes(){
    for(int i=2;i<=10000;i++){
        num[i]=true;
    }
    for(int i=4;i<=10000;i+=2){
        num[i]=false;
    }
    for(int i = 3;i <= N;i+=2){ 
        if(num[i] == true){
            for(int j= 2*i ;j <= N;j += i){
                num[j] = false;
            }
        }
    }
}