目录

• 1. 判断素数（素性测试）
  • 1. $O(\sqrt n)$ 试除
  • 2. Miller-Rabin 素性测试

1. 判断素数（素性测试）

1. \(O(\sqrt n)\) 试除

bool isprime(int n)
{
	if (n<2) return false;
	for (int i=2;i*i<=n;i++)
		if (!(n%i)) return false;
	return true;
}

2. Miller-Rabin 素性测试

Theorm 1

若 \(n\) 是素数，则对于任意 \(1\le a\le n\)，设 \(n-1=d\cdot 2^r\)，则

\[a^d\equiv 1\pmod n\;,\;{\large \exists}_{0\le i\le r}\,a^{d\cdot 2^i}\equiv -1\pmod n \]

中至少有一个成立 .

随便找若干个数 \(a\) 进行判定，很大概率对（4~8 个在 long long 范围稳了）（取质数效果较好）

时间复杂度 \(O(k\log^2 n)\)

const int PrimeList[]={2,3,5,11,37,43,67,73,97}; // for Miller-Rabin
ll qmul(ll a,ll n,ll P)
{
	ll ans=0; if (!n) return 0;
	while (n)
	{
		if (n&1) ans=(ans+a)%P;
    	n>>=1; a=(a+a)%P;
	} return ans%P;
}
ll qpow(ll a,ll n,ll P)
{
	ll ans=1;
	while (n)
	{
		if (n&1) ans=qmul(ans,a,P)%P;
		n>>=1; a=qmul(a,a,P)%P;
	} return ans;
}
bool miller_rabin(ll n,int a)
{
	ll d=n-1,r=0;
	while (!(d&1)){++r; d>>=1;}
	ll x=qpow(a,d,n);
	if (x==1) return true;
	for (int i=0;i<r;i++)
	{
		if (x==n-1) return true;
		x=qmul(x,x,n)%n;
	} return false;
}
bool MillerRabin(ll n)
{
	if (n<2) return false;
	for (int i=0;i<9;i++)
	{
		if (n==PrimeList[i]) return true;
		if (n%PrimeList[i]==0) return false;
		if (!miller_rabin(n,PrimeList[i])) return false;
	} return true;
}