RT，我的Miller-Rabin算法：

int qcheng(int a,int b,int c)//快速积
{
	int ans=0,res=a;
	while(b)
	{
		if(b&1/*=b%2==1*/) ans=(ans+res)%c;
		res=(res+res)%c;
		b>>=1/*=b/=2*/;
	}
	return ans;
}
int qmi(int a,int b,int c)//快速幂
{
	int ans=1,res=a;
	while(b)
	{
		if(b&1) ans=qcheng(ans,res,c);
		res=qcheng(res,res,c);
		b>>=1;
	}
	return ans;
}
int prime[]={2,3,5,7,11,13,17,19,23,29};
bool sushu(int x)//快速判断素数
{
	int s=0,t=x-1;
	if(x==2) return true;//2是素数
	if(x<2 || !(x&1)) return false;//如果x是偶数或者是0,1，那它不是素数
	while(!(t&1)/*=t%2==0*/)//将x分解成(2^s)*t的样子
	{
		s++;
		t>>=1;
	}
	for(int i=0;(i<10 && prime[i]<x);i++)//随便选一个素数进行测试
	{
		int a=prime[i],k,b=qmi(a,t,x);//先算出a^t
		for(int j=1;j<=s;j++)//然后进行s次平方
		{
			k=qcheng(b,b,x);//求b的平方
			if(k==1 && b!=1 && b!=x-1) return false;//用二次探测判断
			b=k;
		}
		if(b!=1) return false;//用费马小定律判断
	}
	return true;//如果进行多次测试都是对的，那么x就很有可能是素数
}

朴素的：

bool sushu(int a)
{
	if(a<2) return 0;
	for(int i=2;i<=sqrt(a);i++)
	{
		if(a%i==0) return 0;
	}
	return 1;
}

对于SP2这题，用Miller-Rabin比朴素的还慢：

Miller-Rabin:https://www.luogu.com.cn/record/45661759

朴素的:https://www.luogu.com.cn/record/45661587

可以看到Miller-Rabin几乎慢了一倍，难道是我的算法写假了？一个复杂度是O(sqrt(sqrt(n)))，一个是O(sqrt(n))

求助大佬们