/* 题目：给出一个数 如果是prime 输出prime 否则输出他的最小质因子 Miller Rabin +Poller Rho 大素数判定+大数找质因子 后面这个算法嘛 基于Birthday Paradox 简单点说就是 在 1到100 内去一个数 ai ai==42的概率很小 但是如果取两个数 ai bi ai-bi==42 的概率就会变大 应用到找素因子上 就不用像试除法那样一个一个的试 但是如果枚举ai bi 显然也很slow 那么有一个非常好使(奇怪)的函数 f(x)=x*x+c 这样将x和f(x)%p作为两个数 看看x-f(x) 与p的关系 这里我们不是试试 p%(x-f(x))==0来找 而是 gcd一下 d=(p,(x-f(x))) d显然是p的因子 然后分解d 这样就ok了 */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #include<cmath> #define ll long long using namespace std; ll T,ans[110],tot; ll init() { ll x=0;char s;s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } ll gcd(ll a,ll b) { return !b?a:gcd(b,a%b); } ll slow_mul(ll a,ll b,ll c)//防止爆掉 { a=a%c;b=b%c; ll an=0; while(b) { if(b&1) { b--; an=an+a; an=an%c; } a<<=1;a=a%c;b>>=1; } return an; } ll Mi(ll a,ll m,ll p) { if(m==0)return 1; ll x=Mi(a,m/2,p)%p; x=slow_mul(x,x,p); if(m&1)x=slow_mul(x,a,p); return x; } ll Pollard_rho(ll p,ll c) { ll i=1,k=2; ll x=rand()%(p-1)+1; ll fx=x; while(1) { i++; x=(slow_mul(x,x,p)+c)%p; ll g=gcd(fx-x+p,p);//防止fx-x<0 if(g!=1&&g!=p)return g;//找到一个因子 if(x==fx)return p;//进入环 换一个随机数 if(i==k) { k=k+k; fx=x; } } } bool Miller_Rabin(ll n) { if(n==2)return 1; if(n==1||!(n&1))return 0; ll m=n-1,j=0; while(!(m&1)) { j++; m=m>>1; } //srand(unsigned(time(0)));丫丫的poj用srand会RE 我看了好久0.0 for(int i=1;i<=10;i++) { ll a=rand()%(n-1)+1; ll x=Mi(a,m,n); for(int k=1;k<=j;k++) { ll y=slow_mul(x,x,n); if(y==1&&x!=1&&x!=n-1)return 0; x=y; } if(x!=1)return 0; } return 1; } void findpri(ll n)//质因数分解n { if(n<=1)return; if(Miller_Rabin(n)) { ans[++tot]=n; return ; } ll p=n; while(p==n)//可能生成的随机数不合适 p=Pollard_rho(p,rand()%(n-1)+1);//返回n的一个因子 findpri(p); findpri(n/p); } int main() { T=init(); while(T--) { ll n=init(); if(Miller_Rabin(n))//素数先来个判断 { printf("Prime "); continue; } memset(ans,0,sizeof(ans));//所有质因子 tot=0; findpri(n);//找质因子 ll an=ans[1]; for(int i=1;i<=tot;i++) an=min(an,ans[i]); printf("%lld ",an); } return 0; }