原文链接：https://blog.csdn.net/qq_43227036/article/details/100336234
OK,前面已经讲了很多判断素数的方法，在判断一个数是否为素数时我们可以采用试除法，但如要求1-n的范围那么时间复杂度很高，所以有了线性的筛法求素数。
但如果为了判断一个大数是否为素数却要消耗很大的空间，这显然会爆空间，那么该如何有效的判断呢？
这里引入两个知识
费马小定理
费马小定理就是说如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。也可以写做a^p ≡ p (mod p).
二次探测
如果p是一个素数，那么使得x^2 ≡ 1 (mod p)的 x的解只有两种可能，就是x = 1 或者 x = p-1。
证明如下：
x^2 ≡ 1 (mod p)可以转换为 x^2-1 = 0（mod p），然后就化为了(x-1)(x+1) = 0 (mod p), 因此p是整除(x-1)(x+1)。因此x = 1 或者 x = p-1。
那么就可以根据二次探测来检验是否为素数，方法如下：
判断n是否为素数
1.根据费马小定理，可以得出a(n-1)%n==1，那么可以把n-1转换成n-1=m*2t，因为n是奇数，所以n-1一定是合数，所以一定可以写成m*2^t,权值m为奇数，否则可以再除以2.
2.从[1，n-1]选取一个数作为a，利用二次探测判断先让y=(am)2,判断y1？
2.1 如果其间y1，但是x!=1||x!=n-1，那么不满足二次探测，是合数
3.循环t次，如果最后x都不等于1，那么一定是合数
4.因为是检测，所以一次判断不一定准确，我们可以多次循环20次，将误差降到最低。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL qul_mul(LL a, LL b, LL mod) {//乘法运算
LL ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return ans;
}
LL qul_pow(LL a, LL b, LL mod) {//快速幂结合乘法运算
LL ans = 1;
while (b) {
if (b & 1) ans = qul_mul(ans, a, mod)%mod;
a = qul_mul(a, a, mod) % mod;
b >>= 1;
}
return ans;
}
bool Miller_Rabin(LL n) {
if (n < 2||!(n&1)) return false;
if (n == 2) return true;
int t=0, m=n-1;
//求n-1=m*2^t
while (!(m&1)) {
t++;
m >>= 1;
}
for (int i = 0; i < 20; i++) {
LL a = rand() % (n - 1) + 1;//[1,n-1]
LL x = qul_pow(a, m, n);//快速幂
//判断每一个x^2%n==1?
for (int j = 0; j < t; j++) {
LL y = qul_pow(x, 2, n);
if (y == 1 && x != 1 && x != n - 1) {//如果y==1，但是x不满足二次探测，则是合数
return false;
}
x = y;
}
//如果最后x还不等于1，则一定是合数
if (x != 1) {
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
if (Miller_Rabin(n)) {
cout << "YES\n";
}
else cout << "NO\n";
return 0;
}