需要的板子：
//**************************************************************** // Miller_Rabin 算法进行素数测试 //速度快，而且可以判断 <2^63的数 //**************************************************************** const int S = 10; //计算x*y%c LL modular_multi(LL x,LL y,LL mo) { LL t; x%=mo; for(t=0;y;x=(x<<1)%mo,y>>=1) if (y&1) t=(t+x)%mo; return t; } //计算num^t%c LL modular_exp(LL num,LL t,LL mo) { LL ret=1,temp=num%mo; for(;t;t>>=1,temp=modular_multi(temp,temp,mo)) if (t&1) ret=modular_multi(ret,temp,mo); return ret; } bool miller_rabbin(LL n) { if (n==2)return true; if (n<2||!(n&1))return false; int t=0; LL a,x,y,u=n-1; while((u&1)==0) t++,u>>=1; for(int i=0;i<S;i++) { a=rand()%(n-1)+1; x=modular_exp(a,u,n); for(int j=0;j<t;j++) { y=modular_multi(x,x,n); if (y==1&&x!=1&&x!=n-1) return false; ///其中用到定理，如果对模n存在1的非平凡平方根，则n是合数。 ///如果一个数x满足方程x^2≡1 (mod n),但x不等于对模n来说1的两个‘平凡’平方根：1或-1，则x是对模n来说1的非平凡平方根 x=y; } if (x!=1)///根据费马小定理,若n是素数，有a^(n-1)≡1(mod n).因此n不可能是素数 return false; } return true; } //************************************************ //pollard_rho 算法进行质因数分解 //************************************************ long long factor[100];//质因数分解结果（刚返回时是无序的） int tol;//质因数的个数。数组小标从0开始 long long gcd(long long a,long long b) { if(a==0)return 1;//??????? if(a<0) return gcd(-a,b); while(b) { long long t=a%b; a=b; b=t; } return a; } long long Pollard_rho(long long x,long long c) { long long i=1,k=2; long long x0=rand()%x; long long y=x0; while(1) { i++; x0=(modular_multi(x0,x0,x)+c)%x; long long d=gcd(y-x0,x); if(d!=1&&d!=x) return d; if(y==x0) return x; if(i==k){y=x0;k+=k;} } } //对n进行素因子分解 void findfac(long long n) { if(miller_rabbin(n))//素数 { factor[tol++]=n; return; } long long p=n; while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1); findfac(p); findfac(n/p); }题目：
/* *判断给出的数是不是素数，如果是输出prim，如果不是则找出最小质因子。 *应该说这两个真是连成套用的。 *板子题 */ #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; //**************************************************************** // Miller_Rabin 算法进行素数测试 //速度快，而且可以判断 <2^63的数 //**************************************************************** const int S = 10; //计算x*y%c LL modular_multi(LL x,LL y,LL mo) { LL t; x%=mo; for(t=0;y;x=(x<<1)%mo,y>>=1) if (y&1) t=(t+x)%mo; return t; } //计算num^t%c LL modular_exp(LL num,LL t,LL mo) { LL ret=1,temp=num%mo; for(;t;t>>=1,temp=modular_multi(temp,temp,mo)) if (t&1) ret=modular_multi(ret,temp,mo); return ret; } bool miller_rabbin(LL n) { if (n==2)return true; if (n<2||!(n&1))return false; int t=0; LL a,x,y,u=n-1; while((u&1)==0) t++,u>>=1; for(int i=0;i<S;i++) { a=rand()%(n-1)+1; x=modular_exp(a,u,n); for(int j=0;j<t;j++) { y=modular_multi(x,x,n); if (y==1&&x!=1&&x!=n-1) return false; ///其中用到定理，如果对模n存在1的非平凡平方根，则n是合数。 ///如果一个数x满足方程x^2≡1 (mod n),但x不等于对模n来说1的两个‘平凡’平方根：1或-1，则x是对模n来说1的非平凡平方根 x=y; } if (x!=1)///根据费马小定理,若n是素数，有a^(n-1)≡1(mod n).因此n不可能是素数 return false; } return true; } //************************************************ //pollard_rho 算法进行质因数分解 //************************************************ long long factor[100];//质因数分解结果（刚返回时是无序的） int tol;//质因数的个数。数组小标从0开始 long long gcd(long long a,long long b) { if(a==0)return 1;//??????? if(a<0) return gcd(-a,b); while(b) { long long t=a%b; a=b; b=t; } return a; } long long Pollard_rho(long long x,long long c) { long long i=1,k=2; long long x0=rand()%x; long long y=x0; while(1) { i++; x0=(modular_multi(x0,x0,x)+c)%x; long long d=gcd(y-x0,x); if(d!=1&&d!=x) return d; if(y==x0) return x; if(i==k){y=x0;k+=k;} } } //对n进行素因子分解 void findfac(long long n) { if(miller_rabbin(n))//素数 { factor[tol++]=n; return; } long long p=n; while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1); findfac(p); findfac(n/p); } //----------------------------------------------// int main() { int t; scanf("%d",&t); LL n; while(t--) { scanf("%lld",&n); if(miller_rabbin(n))puts("Prime"); else { tol = 0; findfac(n); LL ans = factor[0]; for(int i = 1; i < tol; ++i)ans = min(ans,factor[i]); printf("%lld\n",ans); } } return 0; }
