题目描述

给你 $n$ 个整数 $a_1,a_2,…,a_n$，判断它们是不是质数。

样例

输入样例1：

2
5
8

输出样例1

Yes
No

前置知识

首先，我们需要知道什么是质数。

质数是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数。

基本思路

根据质数的定义，我们可以写出最简单的判定质数的算法：

bool prime(int n) {
    if (n < 2)  
        return 0; //小于2的数，既不是质数，也不是合数

    for (int i = 2; i < n; ++i) { //从1遍历到n-1，如果i能整除n，说明n不是质数
        if (n % i == 0)
            return 0;
    }
    return 1;
}

这个代码的时间复杂度是 $O(n)$ 的。

我们可以发现，如果 $d$ 能整除 $n$，那么 $\dfrac{n}{d}$ 也能整除 $n$.

证明：设 $n=rd$（ $r,d$ 均为大于等于 $2$ 的正整数），则 $\dfrac{n}{d}=r$. 因为 $n=rd$，所以 $r$ 也能整除 $n$，即 $\dfrac{n}{d}$ 也能整除 $n$.

所以我们只需要遍历到 $1$ 到 $\sqrt{n}$ 之间的数就可以了。

bool prime(int n) {
    if (n < 2)  
        return 0; //小于2的数，既不是质数，也不是合数

    for (int i = 2; i <= n/i; ++i) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

事实上，终止循环的条件 i <= n/i 还有很多种写法：i <= sqrt(n) 或 i * i <= n. 但 sqrt() 函数比较慢，i * i 容易溢出，所以 i <= n/i 是最佳的写法。

这个算法的时间复杂度是 $O(\sqrt{n})$ 的。

完整代码

#include <iostream>
#include <cstdio>

using namespace std;

bool prime(int n) {
    if (n < 2)  
        return 0; //小于2的数，既不是质数，也不是合数

    for (int i = 2; i <= n/i; ++i) { //遍历到sqrt(n)
        if (n % i == 0)
            return 0;
    }
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n --) {
        int t;
        scanf("%d", &t);
        if (prime(t))  
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}