求最小素因子（pollard-rho）

#include<cstdio>
#include<cstring>
//#include<ctime>
#include<algorithm>
#define LL long long
using namespace std;

inline LL mul(LL a,LL b,LL c)
{return ((a * b - (LL)((long double)a/c*b+1e-8)*c) % c + c ) % c;}
inline LL gcd(LL a,LL b){ return !b ? a : gcd(b , a % b); }
inline LL Pow(LL a,LL b,LL c){
	LL ret = 1;
	for(;b;b>>=1,a=mul(a,a,c)) if(b&1) ret = mul(ret , a , c);
	return ret;
}
const int base[]={2,3,7,31,61,24251};
inline bool Miller_Rabin(LL x)
{
	if(x<2) return 0;
	for(int i=0;i<6;i++) if(base[i]==x) return 1;
	LL res=x-1,k=0,now=0,pre=0,tim;
	for(;!(res&1);res>>=1,k++);
	for(int i=0;i<6 && base[i] < x;i++)
	{
		pre=Pow(base[i],res,x);
		for(tim=k;tim && pre!=1;tim--,pre=now)
			if((now=mul(pre,pre,x))==1 && pre!=1 && pre!=x-1) return 0;
		if(pre!=1) return 0;
	}
	return 1;
}
inline LL Rho(LL x)
{
	LL a=rand()+1,b=a,i=1,j=1,d=1,tmp=1,c=rand()+3;
	for(;d==1;i++)
	{
		a=mul(a,a,x)+c;
		(a>=x) && (a-=x);
		tmp = mul(tmp , abs(b-a) , x);
		(i==j) && (b=a,j<<=1,d=gcd(tmp,x));
		(!(i&1023)) && (d=gcd(tmp,x));
	}
	return (d==x ? Rho(x) : d);
}
LL Max = 0;
inline void Pollard(LL x,LL tmp=0)
{
	if(x <= Max || x==1) return;
	if(Miller_Rabin(x)){ Max = x;return; }
	Pollard(x/(tmp=Rho(x))),Pollard(tmp);
}

int main()
{
	int T;LL n;
	srand(12345);
	for(scanf("%d",&T);T--;)
	{
		scanf("%lld",&n);
		Max = 0;
		Pollard(n);
		if(Max == n) puts("Prime");
		else printf("%lld\n",Max);
	}
}
           

Pollard_Rho的實際表現其實很大部分上取決于Rho的速度。。。。

然後你需要寫一個短小精悍的Rho。

1：Rho中的判相遇實際上就是取gcd，但是gcd雖然常數小但是也不能忽略那個log，

可以把a-b的積存下來，每隔127或1023次取一次gcd。。。。這個優化是最強的。