[PTA] 判断素数（C++，数学）

本题的目标很简单，就是判断一个给定的正整数是否素数。

输入格式：

输入在第一行给出一个正整数N（$\le 10$），随后N行，每行给出一个小于2312^{31}231的需要判断的正整数。

输出格式：

对每个需要判断的正整数，如果它是素数，则在一行中输出Yes，否则输出No。

输入样例：

2
11
111

输出样例：

Yes
No

解题思路：

首先，我们尝试使用常见的素数判断方法

for (int i = 2; i * i <= num; i++) {if (num % i == 0) {ans = false;break;}
}

计算一下时间复杂度O(10∗231)≈O(105.5)O(10*\\sqrt{2^{31}})≈O(10^{5.5})O(10∗231​)≈O(105.5)，是可行的

但是跑起来会$TLE$，为什么呢？

返回题干查看数据范围，发现最大输入是231−12^{31}-1231−1

那么再看一看我们的循环停止条件i * i <= num，我们知道i * i是int类型

但是对于最大输入这个条件不可能为false，因为不可能存在int类型的数据比231−12^{31}-1231−1大，爆精度了

这个$bug$好修，开long long

然后再次提交发现答案错误

$emmm$，再回到题干，发现输入为正整数，也就是说可以输入$1$

对于$1$，我们进行特殊判定即可

最后，AC代码如下

#include <iostream>
using namespace std;
const int max_n = 10;
const int max_num = 1 << 31 - 1;int main() {int n;cin >> n;for (int i = 0; i < n; i++) {long long num;cin >> num;if (num == 1) {cout << "No" << endl;continue;}bool ans = true;for (long long j = 2; j * j <= num; j++) {if (num % j == 0) {ans = false;break;}}if (ans) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

这里在附加上几个更高效的素数判定方法

（1）比较玄学的判定方法

bool is_prime(int num) {if (num <= 3) return num > 1;if (num % 6 != 1 && num % 6 != 5) return false;for (int i = 5; i * i <= num; i += 6)if (num % i == 0 || num % (i + 2) == 0)return false;return true;
}

（2）费马小定理：

在$modp$意义下，如果$p$为质数并且$b$不是$p$的倍数

则有bp−1modp≡1b^{p-1}\\ mod\\ p\\equiv 1bp−1 mod p≡1

#include <iostream>
using namespace std;long long quick_expo(long long a, long long b, long long mod_num) {/* 快速幂 */long long ret = 1;while (b != 1) {if (b & 1) ret = (ret * a) % mod_num;a = (a * a) % mod_num;b >>= 1;}return (ret * a) % mod_num;
}int main() {int n;long long a = 2;cin >> n;for (int i = 0; i < n; i++) {long long num;cin >> num;if (num == 2) {cout << "Yes" << endl;continue;}if (num == 1) {cout << "No" << endl;continue;}if (a * quick_expo(a, num - 2, num) % num == 1) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}