题意：求一个整数是否是素数，如果不是，则输出它最小的质因数。
分析：
判断一个大整数是否为素数用Miller_rabin算法，求一个大整数的所有质因数用Pollard_rho算法。这题就是直接套模板。
另外这里的gcd和pow_mod不能用一般的方式，T了。代码里我注释掉的就是T了的写法。
代码：
#include<iostream>#include<cmath>#include<ctime>#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;int t;ll n,prim[1000];ll ans;int tot;ll mul_mod(ll a,ll b,ll c){ll t=0;a%=c;b%=c;while(b){if(b&1){t=(t+a)%c;}a<<=1;a%=c;b>>=1;}return t;}//ll pow_mod(ll a,ll b,ll c)//{//ll t=1;//while(b){//if(b&1) t=(t*a)%c;//b>>=1;//a=(a*a)%c;//}//return t;//}ll pow_mod(ll x,ll n,ll mod){if (n==1) return x%mod;int bit[90],k=0;while (n){bit[k++]=n&1;n>>=1;}ll ret=1;for (k=k-1;k>=0;k–){ret=mul_mod(ret,ret,mod);if (bit[k]==1) ret=mul_mod(ret,x,mod);}return ret;}bool check(ll a,ll n,ll x,ll t){ll ret=pow_mod(a,x,n);ll tmp=ret;for(int i=0;i<t;i++){ret=mul_mod(ret,ret,n);if(ret==1&&tmp!=1&&tmp!=n-1) return true;tmp=ret;}if(ret!=1) return true;return false;}bool Miller_rabin(ll n){ll x=n-1,t=0;while((x&1)==0){x>>=1;t++;}int ok=1;if(t>=1&&(x&1)){for(int i=0;i<20;i++){ll a=rand()%(n-1)+1;if(check(a,n,x,t)){ok=1;break;}ok=0;}}if(!ok||n==2) return false;return true;}//ll gcd(ll a,ll b)//{//if(b==0) return a;//return gcd(b,a%b);//}ll gcd(ll a,ll b){if (a==0) return 1;if (a<0) return gcd(-a,b);while (b){ll t=a%b; a=b; b=t;}return a;}ll Pollard_rho(ll x,ll c){ll i=1,k=2;ll x0=rand()%x,y=x0;while(1){i++;x0=(mul_mod(x0,x0,x)+c)%x;ll d=gcd(y-x0,x);if(d>1&&d<x) return d;if(y==x0) return x;if(i==k){y=x0;k+=k;}}}void findfac(ll n){if(!Miller_rabin(n)){prim[tot++]=n;return;}ll p=n;while(p>=n) p=Pollard_rho(p,rand()%(n-1)+1);findfac(p);findfac(n/p);}int main(){srand(time(NULL));scanf("%d",&t);while(t–){scanf("%lld",&n);if(!Miller_rabin(n)){printf("Prime\n");continue;}tot=0;findfac(n);ans=prim[0];for(int i=1;i<tot;i++){ans=min(ans,prim[i]);}printf("%lld\n",ans);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，而是深沉的意志恢弘的想象炙热的恋情；青春是生命的深泉在涌流。
