素数筛

素数是大于1，并且除了1和它本身不能被其他自然数整除的自然数。

最小的自然数是2，也是唯一的偶素数；

1、暴力枚举（n<1e4）

#include<bits/stdc++.h>
using namespace std;
# define int long long
//判断单个数字是不是素数
int isp(int num){
	if(num<2){
		return 0;//小于2的都不是素数
	}
	//只遍历到根号num,减少循环次数
	for(int i=2;i*i<num;i++){
		if(num%i==0){
			return 0;//能被整除的就不是素数，结束
		}
	}
	return 1;//是素数
}
signed main(){
	int x;
	cin>>x;
	if(isp(x)){//调用函数判断是不是素数
		cout<<"Y";
	}
	else{
		cout<<"N";
	}
	return 0;
}

2、埃氏筛

定义一个布尔数组isp[],isp[i]表示数字i是否是素数，初始全设置为素数，为真

从最小的素数2开始，将所有2的倍数标记为假

依次遍历后续数字，如果当前是素数，就标记素数所有的倍数为假

最终数组中值为真的下标，就是1到N中所有的素数

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=10005;
bool isp[N];
void solve(){
	//初始化：先默认所有的数都是素数，为真
	for(int i=2;i<N;i++){
		isp[i]=true;
	}
	for(int i=2;i*i<N;i++){
		if(isp[i]){//如果i是素数，标记它的所有倍数为假
			for(int j=i*i;j<N;j+=i){
				isp[j]=false;
			}
		}
	}
}
signed main(){
	solve();
	int x;
	cin>>x;
	if(isp[x]){
		cout<<"y"<<endl;
	}
	else{
		cout<<"n";
	}
	return 0;
}