题目内容

给定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的整数中，如果只包含1和本身这两个约数，这个数被称为质数或者叫做素数。
利用试除法来对质数进行判定。

由于有d整除n，那么一定有(n/d)整除n，因此只需要试除小于n/d的数即可。

代码

#include <iostream>
#include <algorithm>

using namespace std;

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i++) //在判断条件中，推荐。不推荐：i <= sqrt(n),i*i < n此类的写法。
        if (n % i == 0)
            return false;
            
    return true;
}

int main(){
    int n;
    scanf("%d", &n);
    while(n --){
        int num;
        scanf("%d",&num);
        bool flag;
        flag = is_prime(num);
        if(flag) puts("Yes");
        else puts("No");
    }
    return 0;
}