埃氏筛

首先将 $2$ 到 $n$ 范围内的整数写下来。

其中 $2$ 是最小的素数。将表中所有的 $2$ 的倍数划去。

表中剩下的最小的数字就是 $3$ ，他不能被更小的数整除，所以 $3$ 是素数。

再将表中所有的 $3$ 的倍数划去……

以此类推，如果表中剩余的最小的数是 $m$，那么 $m$ 就是素数，然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举 $n$ 以内的素数。

时间复杂度：$O(n \log \log n)$

code

#include<bits/stdc++.h>
using namespace std;
bool vis[1000005];
void prime(int n){
	vis[0]=vis[1]=0;//0和1不是质数
	for(int i=2;i<=n;i++){//从2枚举
		if(vis[i])//如果i是质数
			for(int j=2*i;j<=n;j+=i)//那么枚举它的倍数
				vis[j]=0;//j不是质数
	}
}
int main(){
	int n;
	cin>>n;
	memset(vis,true,sizeof(vis));
	prime(n);
	cout<<(vis[n]?"yes":"no");
}