试除法判断质数_给定 n 个正整数 ai,判定每个数是否是质数。 输入格式 第一行包含整数 n。 接下来

给定 nn 个正整数 aiai，判定每个数是否是质数。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个正整数 aiai。

输出格式

共 nn 行，其中第 ii 行输出第 ii 个正整数 aiai 是否为质数，是则输出 Yes，否则输出 No。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤231−11≤ai≤231−1

输入样例：

2
2
6

输出样例：

Yes
No

 主要考虑如何降低复杂度，防止tle

#include <iostream>
 
using namespace std;
 
int judge(int x) {
    if (x == 1) return 0;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) return 0;
    }
    return 1;
}
int main() {
    int n;
    cin >> n;
    while (n --) 
    {
        int x;
        cin >> x;
        if (judge(x)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

只需要保证i * i <= n 即可，但是i * i容易溢出int的范围，所以改成i* i<= n, 为什么要写成i * i呢，是因为比如24， 12是他的因数， 24 / 12 = 2, 24 % 12 == 0， 其实在 2 (比sqrt(24)小） 的时候就判断出来了。

挺基础的数论知识。