AcWing 866. 试除法判定质数

题目

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

输入格式 第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个正整数 $a_i$。

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

数据范围 $1≤n≤100,1≤a_i≤2^{31}−1$ 输入样例：

2
2
6

输出样例：

Yes
No

思路

1. 为什么可以遍历$2...x^{1/2}$来确认 对于某个数 $x$，$1、x$为一对因数，我们可以用没对因数的左点i，可以同时验证一对因数。最小的一对左部因数必然 $<= x^{1/2}$，否则两个因数乘积大于 $x$
2. 为什么不用 $i * i <= x$ 而是 $i <= x / i$ $i * i <= x$情况下，当x接近类型最大值max时，若$i * i <= max, (i + 1) * (i + 1) > max$，此时数值溢出，会影响对结果的判断

代码

#include <iostream>

using namespace std;

int n, a;

bool is_prime(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()
{
    cin >> n;
    
    while (n -- )
    {
        cin >> a;
        if (is_prime(a)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}