acwing 866. 试除法判定质数

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

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

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

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

数据范围
1≤n≤100,
1≤ai≤2³¹−1

输入样例：
2
2
6
输出样例：
Yes
No

方法1: 直接暴力枚举 O(n²)
但是要求高一点就会超时

bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i=2; i <= n; i++)    
        if(n % i == 0)
            return false;
    return true;
}
1
2
3
4
5
6
7
8

优化思路： 只需要遍历一半
因为d|n 时， n/d|n 也行；其中d 表示因子，n表示一个数， | 表示整除
整理得： d <= n/d 即可；得 d * d <= n 即可，
故，在找因子时候，只需要遍历根号n部分即可

方法2：直接使用sqrt函数

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    for(int i = 2;i <= sqrt(n);i ++){ //优化部分
        if(n % i == 0){  //如果可以被i整除，说明这个数不是质数
            return false;  //返回不是
        }
    }
    return true; //返回是
}
1
2
3
4
5
6
7
8
9

但是，这个sqrt 函数底层运行很慢，每次执行这行代码时，需要运算一次，下面看看其他方法

方法3：
将遍历代码优化成for(int i = 2;i * i <= n;i ++), 本质上跟上面差不多，但是这里可能会出现溢出的风险，不推荐

方法4：
将遍历代码优化成for(int i=2; i <= n / i; i++), 原理跟上面的一样，但这里不会出现数据溢出的风险，推荐使用这种

推荐方法完整代码

#include <iostream>

using namespace std;

// 试除法
// 将O(n) 降到为 O(sqrt(n))
bool is_prime(int n)
{
    if(n < 2) return false;
    // for(int i=2; i * i <= n; i++)    // 可能有溢出风险
    // for(int i=2; i <= sqrt(n); i++)  // sqrt 函数每次计算，影响效率
    for(int i=2; i <= n / i; i++)   // 只需要判断两个中较小的一个约数就行了
        if(n % i == 0)
            return false;
    return true;
}

int main()
{
    int m;
    cin >> m;
    while(m --)
    {
        int c;
        cin >> c;
        if(is_prime(c)) puts("Yes");
        else puts("No");
    }
    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
27
28
29
30
31