往期回顾：
上一次我们学习了时间复杂度为O(nloglogn)的质数筛算法埃氏筛，他是先默认所有数都是质数，然后没找到一个质数，就把范围内所有它的倍数都设为合数来进行筛选的。
但是不知你们有没有发现它有一个漏洞，就是有的数会筛两遍，例如 6 ，他在找到2的时候筛一次，但找到 3 的时候又筛了一次，这可不行，所以我们今天要学习欧拉筛。
算法思路：
先默认所有数都是质数，然后找到一个数n后，如果n是第i个质数，就把质数表的第i项赋值为这个质数，接下来不论是质数还是合数都乘上质数表中的质数，直到质数表中的数是n的因数。
代码实现
如果要把所有数都默认为质数，就需要一个指数数组bool zs[100000010];，真值为质数，假值为合数。接下来我们要把它用真值初始化，可以用到memset(zs,1,sizeof(zs));，但是千万不要漏掉头文件：#include<cstring>或万能头文件#include<bits/stdc++.h>。同样，我们需要把0，1赋值为假值，用zs[0] = zs[1] = 0;来实现。
接下来就到了重中之重
下一步就和埃氏筛不一样了。for循环，从2开始，到 n 结束，每次加一然后就要实现“如果n是第i个质数，就把质数表的第i项赋值为这个质数”看到这里，我们就发现还要一个“质数表”并且不能利用循环中定义的数(因为合数也会执行)，还要加上表示质数个数的变量，就像这样：
int zsb[9000010];//质数表：用于记录已找出的质数
int sum = 0;//找出的质数个数
//并且要给质数表赋初始值以免出错
memset(zsb,0,sizeof(zsb));
变量和数组都有了，接下来就是判断如果是质数，把质数表的第sum项赋值为这个质数，并把sum加一。可以写成这样：
if(zs[i] == 1){
zsb[sum++] = i;
}
接下来就是找倍数了。还是要用到for循环，但注意嵌套for循环要用另一个变量名。从0开始，一直找到最后一个质数表中的质数，并且找到的数i乘质数表的第j项要小于最大范围n不然有些是没有意义的用代码for(int j = 0; j < sum && i*zsb[j] <= n; j++)来实现，再把指数数组zs中的第i*质数表的第j项赋值为零来实现。然后就要判断这次乘上的质数是不是找的数i的因数，如果是就退出循环，不是则继续乘质数表的下一个数。代码，走你┏ (゜ω゜)=☞
for(int j = 0; j < sum && i*zsb[j] <= n; j++){
zs[i*zsb[j]] = 0;
if(i % zsb[j] == 0){
break;
}
}
最后加上一个return；就ok了。
完整代码
不要抄袭！！！
这是一个函数版的欧拉筛，使用的时候要在主函数内调用。
要求质数个数的话，就直接输出sum就OK了。是不是很方便呢？
bool zs[100000010];//指示数组：下标为找的数，真为质数，假为合数。
int zsb[9000010];//质数表：用于记录已找出的质数
int sum = 0;//找出的质数个数
//如果要求质数个数，直接输出sum
void ols(int n){//欧拉筛
memset(zs,1,sizeof(zs));//初始化，假设全部为真值(质数)
memset(zsb,0,sizeof(zsb));//初始化，防止出错
zs[0] = zs[1] = 0;//初始化，0和1不是质数也不是合数
for(int i = 2; i <= n; i++){
if(zs[i] == 1){//如果有质数
zsb[sum++] = i;//质数表的第sum项赋值为这个质数
}
for(int j = 0; j < sum && i*zsb[j] <= n; j++){//找倍数
zs[i*zsb[j]] = 0;//乘上质数表的第i项
if(i % zsb[j] == 0){//如果是质数表第i项的倍数
break;//退出
}
}
}
return;
}