前置芝士：
例·1 素数个数：
运用上一篇的知识，可得出以下代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e8+5;
int n,ans;
bool prime(int x){
if(x==1){
return 0;
}
if(x==2){
return 1;
}
for(int i=2;i*i<=x;i++){
if(x%i==0){
return 0;
}
}
return 1;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
if(prime(i)){
ans++;
}
}
cout<<ans<<endl;
return 0;
}
但，当我们把这串代码提交的时候……
所以，我们要吸氧优化！
主角——埃氏筛：
为什么叫埃氏筛我不知道，应该是一个姓埃的人发明的，但，原理我是懂的。
埃筛的思路：
对于每一个数，如果他是质数，则将它的倍数标为不是质数。
看着很含糊，仔细讲一下：
设现在有\(1-10\)十个数
\(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\)
首先，1不是质数
\(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\)
\(n\ y\ y\ y\ y\ y\ y\ y\ y\ y\)
下一个，2现在是质数，将2的倍数标为不是质数
\(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\)
\(n\ y\ y\ n\ y\ n\ y\ n\ y\ n\)
下一个，3现在是质数，将3的倍数标为不是质数
\(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\)
\(n\ y\ y\ n\ y\ n\ y\ n\ n\ n\)
下一个，4现在不是质数，跳过
下一个，5现在是质数，将5的倍数标为不是质数
\(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\)
\(n\ y\ y\ n\ y\ n\ y\ n\ n\ n\)
下一个，6现在不是质数，跳过
下一个，7现在是质数，将7的倍数标为不是质数
\(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\)
\(n\ y\ y\ n\ y\ n\ y\ n\ n\ n\)
下一个，8现在不是质数，跳过
下一个，9现在不是质数，跳过
下一个，10现在不是质数，跳过
下一个，11超出边界，结束
-----------------------------------------------华丽的分割线-----------------------------------------------
经过刚才的捣鼓，我们可以理解埃筛了
code:
void Prime(){
vis[0]=1;//0不是质数
vis[1]=1;//1不是质数
for(int i=2;i<=maxn;i++){//筛出2~maxn的所有质数
if(vis[i]==0){//之前没被标记过
for(int j=i+i;j<=maxn;j+=i){//从i+i开始，将i的倍数标记为不是质数
vis[j]=1;//标记
}
}
}
}
如何判断一个数是不是质数
很简单，如果vis[i]==0，那么是质数，否则不是质数
例·1代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e8;
int n,sum;
bool vis[maxn];
void Prime(){
vis[0]=1;//0不是质数
vis[1]=1;//1不是质数
for(int i=2;i<=maxn;i++){//筛出2~maxn的所有质数
if(vis[i]==0){//之前没被标记过
for(int j=i+i;j<=maxn;j+=i){//从i+i开始，将i的倍数标记为不是质数
vis[j]=1;//标记
}
}
}
}
int main(){
Prime();//调用函数
sum=0;//清空
cin>>n;//输入
for(int i=1;i<=n;i++){//枚举
if(vis[i]==0){//是质数
sum++;//数量++
}
}
cout<<sum;//输出
return 0;
}