Miller-Rabin素性测试

博主链接

/*

*  随机素数测试（伪素数原理理）

*  CALL: bool res = miller(n);

*  快速测试n是否满⾜足素数的“必要”条件，出错概率极低

*  对于任意奇数n > 2和正整数s，算法出错概率≤2^(-s)

*/ 

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 2*1e5 + 5;
long long quicks(long long  a, long long b, long long c){
	long long ans = 1;
	a = a % c;
	while (b != 0){
		if (b & 1) ans = (ans*a) % c;
		b >>= 1;
		a = (a*a) % c;
	}
	return ans;
}
bool Miller_Rabin_1(long long n) {  //标准代码 
	long long t = 0;
	long long b = n - 1;
	while ((b & 1) == 0){
		t++;
		b >>= 1;
	}
	//现在的a^(b*2^t)=1(mod n)
	long long a = rand() % (n - 1) + 1;   //测试
	long long x = quicks(a, b, n);
	//个人认为这里如果加上优先判定是不是1，n-1的话，会更快一点？是不是呢？？？？？ 
	for (long long i = 1; i <= t; i++){
		long long y = quicks(x, 2, n);
		if (y == 1 && x != 1 && x != n - 1) return false;    //这里的意思是如果a^(d*2^r)是1，但是a^(d*2^(r-1))不是1也不是n-1的情况，这时候我们认为是合数 
		x = y;
	}
	if (x != 1) return false;
	else return true;
}
int main() {
	ll n;
	cin >> n;
	if (Miller_Rabin_1(n))cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}