题意：给定N，如果N为素数，输出“Prime”,否则输出其最小因子。
思路：用miller_rabin判断素数，pollardRho用于整数因子的分解。整数因子分解还有一个更快的算法：SQUFOF。
#include
#include
#include
#include
#include
#define time 8
#define call 200
using namespace std;
__int64 min_num;
//============================素数判断====================================//
__int64 mod_mult(__int64 a,__int64 b,__int64 n)//返回 (a*b)%n
{
a=a%n;
__int64 res=0;
while(b)
{
if(b&1)
{
res+=a;
if(res>=n) res-=n;
}
a=a<<1;
if(a>=n) a-=n;
b=b>>1;
}
return res;
}
__int64 mod_exp(__int64 a,__int64 b,__int64 n)//返回(a^b)mod n
{
a=a%n;
__int64 res=1;
while(b>=1)
{
if(b&1)
res=mod_mult(res,a,n);
a=mod_mult(a,a,n);
b=b>>1;
}
return res;
}
bool witness(__int64 a,__int64 n)
{
__int64 m,x,y;
int i,j=0;
m=n-1;
while(m%2==0)
{
m=m>>1;
j++;
}
x=mod_exp(a,m,n);
for(i=1;i<=j;i++)
{
y=mod_exp(x,2,n);
if(y==1&&x!=1 &&x!=n-1) return true;//二次探测
x=y;
}
if(y!=1)
return true;
return false;
}
bool miller_rabin(__int64 n,int s)
{
if(n==1) return true;
if(n==2) return false;
if(n%2==0) return true;
for(int i=1;i<=s;i++)//s次试探
{
__int64 a=rand()%(n-1)+1;
if(witness(a,n))
return true;
}
return false;//为素数
}
//=======================分解整数因子============================================//
__int64 gcd(__int64 a,__int64 b)
{
if(b==0) return a;
return gcd(b,a%b);
}
__int64 pollardRho(__int64 n,int c)
{
int i=1;
__int64 x=rand()%n;
__int64 y=x;
int k=2;
while(1)
{
i=i+1;
x=(mod_exp(x,2,n)+c)%n;
__int64 d=gcd(y-x,n);
if(1
if(y==x) return n;
if(i==k)
{
y=x;
k=k*2;
}
}
}
void getsmallest(__int64 n,int c)
{
if(n==1) return ;
if(miller_rabin(n,time)==false)//如果为素数
{
if(n
return ;
}
__int64 val=n;
while(val==n)
val=pollardRho(n,c--);
getsmallest(val,c);//二分
getsmallest(n/val,c);
}
//======================================================================//
int main()
{
int test;
cin>>test;
__int64 n;
while(test--)
{
scanf("%I64d",&n);
if(miller_rabin(n,time)==false )
cout<
else
{
min_num=n;
getsmallest(n,call);
cout<
}
}
return 0;
}
