埃氏筛

首先将 $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");
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int j,q,k,a;
	cin>>j;
	for(int i=2;i<j;i++)
	if(j%i==0)
	{
		cout<<"no";
		return 0;
	}
	cout<<"yes";
	return 0;
}

#include<bits/stdc++.h> using namespace std; bool sushu(int a) { if(a1) return false; for(int i=2;i*i<=a;i++) { if(a%i0) return false; } return true; } int main() { int r; cin>>r; if(sushu(r)) { cout<<"yes"; } else { cout<<"no"; } return 0; }

555

#include<bits/stdc++.h> using namespace std; bool sushu(int n) { if(n1)return false; for(int i=2;i*i<=n;i++) { if(n%i0) return false; } return true; } int main() { int n; cin>>n; if(sushu(n)) { cout<<"yes"; } else cout<<"no"; return 0; }

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i,d;
	cin>>n;
	if(n>=1&&n<=100000)
	{
		for(i=1;i*i<=n;i++)
		{
			if(n%i==0&&i!=1)
			{
				d=0;
				break;
			}
			if(n%i!=0)
			{
				d=1;
			}
		}
		if(d==1&&i!=1)
		{
			cout<<"yes"<<endl;
		}
		else if(d==0)
		{
			cout<<"no"<<endl;
		}
	}
	return 0;
}

利用方根的方法我这里总是过不了 所以我选择无脑硬取余

#include<bits/stdc++.h> using namespace std; bool sushu(int n) { if(n1)return false; //1²»ÊÇËØÊý for(int i=2;i*i<=n;i++)//¼ìÑé1µ½x¿ª¸ùºÅ¼´¿É { if(n%i0) return false;//±»iÈ¡ÓàΪ0£¬²»ÊÇËØÊý } return true; }//¶¨ÒåËØÊýº¯Êý int main() { int n; cin>>n; if(sushu(n)) { cout<<"yes"; } else cout<<"no"; return 0; }

#include<bits/stdc++.h>
using namespace std;
int sushu(int a)
{
	int b;
	for(int i=2;i*i<=a;i++)
	{
		if(a%i==0)
		{
			b=1;
			break;
		}
		else
		if(a%i!=0)
		{
			b=0;
		}
	}
	if(b==0&&a!=1)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
int main()
{
	int n;
	cin>>n;
	if(sushu(n)==1)
	{
		cout<<"yes";
	}
	else
	if(sushu(n)==0)
	{
		cout<<"no";
	}
}