【ACWing】866. 试除法判定质数_acwing 866. 试除法判定质数

题目地址：

https://www.acwing.com/problem/content/868/

给定$n$个正整数$a_i$，判断其是否是质数。

输入格式：
第一行包含整数$n$。接下来$n$行，每行包含一个正整数$a_i$。

输出格式：
共$n$行，其中第$i$行输出第$i$个正整数$a_i$是否为质数，是则输出“Yes”，否则输出“No”。

数据范围：
$1\le n\le 100$
$1\le a_i\le 2^{31}-1$

容易证明，如果$x$不是质数，那么$x$一定有位于$[2,\sqrt{x}]$的质因子。所以可以用试除法，对于每个$x$，如果$x<2$则不是质数，否则从$2$开始遍历到$\sqrt{x}$，只要发现某个$x$的因子，则返回false。但是在写代码的时候，循环最好应当写成：

for (int i = 2; i <= n / i; i++) 
1

这样可以避免使用sqrt函数，并且可以防止溢出。代码如下：

#include <iostream>
using namespace std;

bool is_prime(int n) {
    if (n < 2) return false;

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

    return true;
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;

        if (is_prime(x)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

每次询问时间复杂度$O(\sqrt{x})$，空间$O(1)$。