X02推荐看看：质数筛
2023-08-12 12:34:55
发布于：江苏
2阅读
0回复
0点赞
前言：这里提供两种方法，仅供参考，时间复杂度O(sqrt(n))
第一种方法：统计素数法
这种方法是传统的数学方法，下面是函数内容
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int n){
int cnt=0;//素数统计变量
for(int i=1;i*i<=n;i++){
if(n%i==0) cnt+=2;
}
return cnt==2;
}
int main(){
int n;
cin>>n;
if(is_prime(n)) cout<<"yes";
else cout<<"no";
return 0;
}
第二种方法：判断能否整除
原理就是从2到n-1判断其中的有没有能够整除的，如果有说明不是素数，没有说明是素数
下面是实现
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int n){
if(n==1) return false;//特殊判断
for(int i=2;i*i<n;i++){
if(n%i==0) return false;
}
return true;
}
int main(){
int n;
cin>>n;
if(is_prime(n)) cout<<"yes";
else cout<<"no";
return 0;
}
这里空空如也
有帮助，赞一个