题目描述
一个大于 1 的自然数,如果除了 1 和它自身外,不能被其他自然数整除则称该数为质数。现在,给定你 N 个大于 1 的自然数,请你依次判断这些数是否是质数。
样例
例如 7 就是一个质数,因为它只能被 1 和 7 整除。
(暴力枚举) 最朴素的做法
会超时,不建议
时间复杂度
O(n)
参考文献
C++ 代码
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--){
int x;
cin>>x;
if(x==2)cout<<x<<" is prime"<<endl;//2是一个特殊的质数,需要拿出来单独判断
else{
for(int i=2;i<=x-1;i++){//从2开始枚举到x-1,如果能被其中的某个数整除,就不是素数
if(x%i==0){
cout<<x<<" is not prime"<<endl;
break;
}
if(i>=x-1)cout<<x<<" is prime"<<endl;//若循环正常结束,则x不能被任一i整除
}
}
}
return 0;
}
(暴力枚举) 改进做法
通过减少枚举量降低时间复杂度来改进
时间复杂度
O(√n)
参考文献
C++ 代码
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--){
int a;
cin>>a;
if(a==2)cout<<a<<" is prime"<<endl;
else{
for(int i=2;i<=sqrt(a)+1;i++){//一个合数必定有一个小于或等于其平方根的质因子由此可以缩小区间为[2,√n],又考虑到浮点数难以精确比较,为了避免误差引起错误,将区间扩大到[2,√n+1]
if(a%i==0){
cout<<a<<" is not prime"<<endl;
break;
}
if(i>sqrt(a))cout<<a<<" is prime"<<endl;
}
}
}
return 0;
}