AcWing 726. 质数
原题链接
中等
作者:
Overmind
,
2021-02-17 13:09:47
,
所有人可见
,
阅读 281
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
void prime(int a){
int count = 0;
for(int i = 2 ; i <= sqrt(a) ; i++ ){ //注意小与等于根号a
//求约数如果 i 是 a 的约数,则 a/i 也是 a 的约数,为了减少复杂度,
//只用枚举一小段,同时为了避免重复枚举,需要保证 i <= a/i ,即只用枚举到 根号a
if( !(a%i) ) count += 1;
}
if( !count ) cout<< a << " is prime" <<endl;
else cout << a << " is not prime"<<endl;
}
int main(){
int n,a;
cin>>n;
for(int i = 0 ; i < n ; i++){
cin>>a;
prime(a);
}
return 0;
}