题目描述

给定 n 个正整数 ai，判定每个数是否是质数。

输入格式

• 第一行包含整数 n。
• 接下来 n 行，每行包含一个正整数 ai。

输出格式

• 共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。

数据范围

• 1 ≤ n ≤ 100
• 1 ≤ ai ≤ 2^31 − 1

输入样例

2
2
6

输出样例

Yes
No

知识点：试除法判断质数

1. 因数成对出现

对于一个正整数 x，如果 x 有一个因数 a，那么必然存在另一个因数 b(b = x / a)，使得 x = a × b。

• 如果 a 小于等于 x 的平方根（sqrt(x)），那么 b 就大于等于 sqrt(x)。
• 如果 a 大于 sqrt(x)，那么 b 就小于 sqrt(x)。

也就是说，所有大于 sqrt(x) 的因数一定能和一个小于等于 sqrt(x) 的因数配对。

2. 检查到 x / i 就足够

• 如果在 i 从 2 到 sqrt(x) 的范围内没有找到能整除 x 的数，说明 x 没有小于等于 sqrt(x) 的因数。
• 那么大于 sqrt(x) 的因数也不会出现，因为它们都已经和小因数配对检查过了。

3. 举例说明

比如 x = 36：

• sqrt(36) = 6
• 因数对有：(2,18)、(3,12)、(4,9)、(6,6)
• 你只需要检查 2, 3, 4, 5, 6，剩下的 9, 12, 18 都和前面的小数配对过了。

结论

所以只要在 [2, sqrt(x)] 这个范围内检查因数就可以了，不会漏掉任何配对的因数。

代码

#include<iostream>

using namespace std;

int n;

bool isprime(int x)
{
    if(x < 2) return false;

    for(int i = 2 ; i <= x / i ; i ++)
        if(x % i == 0) return false;    

    return true;
}

int main()
{
    scanf("%d",&n);

    while(n --)
    {
        int x;
        scanf("%d",&x);

        if(isprime(x)) printf("Yes\n");
        else printf("No\n");
    }
}