笔记
- 质数必大于1
- 时间复杂度O(n)
- 若存在一个大于sqrt(x)的因数,那么必定存在小于sqrt(x)的因数
代码
#include<iostream>
using namespace std;
bool IsPrime(int x) {
if(x < 2) return false; //质数必大于1
for(int i = 2; i <= x / i; i++) {//若存在一个大于sqrt(x)的因数,那么必定存在小于sqrt(x)的因数
if(x % i == 0) {
return false;
}
}
return true;
}
int main() {
int n;
scanf("%d", &n);
while(n--) {
int x;
scanf("%d", &x);
if(IsPrime(x)) puts("Yes");
else puts("No");
}
return 0;
}