给定 n 个正整数a_i,判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 a_i。
输出格式
共 n 行,其中第 i 行输出第 i个正整数 a_i 是否为质数,是则输出 Yes,否则输出 No。
数据范围
1\le n\le 100,1\le a_i\le 2 ^ {31} - 1
输入样例:
2
2
6
输出样例:
Yes
No
时间复杂度
O(\sqrt{n})
核心思想
枚举一遍就好了
核心函数
bool is_pr(int x){
if(x < 2)
return false;
for(long long i = 2; i * i <= x; i ++)
if(x % i == 0)
return false;
return true;
}
代码实现
#include <iostream>
using namespace std;
bool is_pr(int x){
if(x < 2)
return false;
for(long long i = 2; i * i <= x; i ++)
if(x % i == 0)
return false;
return true;
}
int main (){
int n;
cin >> n;
while(n --)
{
int x;
cin >> x;
cout << (is_pr(x) ? "Yes" : "No") << endl;
}
return 0;
}