涉及到大数的素性判定及大数的质因数分解，感觉用处不大。当成一块模板好了
#include <cstdio> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; #define abs(a) (a)>=0? (a):(-a) const int S=20; LL qmut(LL a,LL b,LL mod) { a%=mod,b%=mod; LL ret=0; for(;b;b>>=1) { if(b&1) ret=(ret+a)%mod; a=(a+a)%mod; } return ret; } LL qpow(LL x,LL n,LL mod) { LL ret=1; for(;n;n>>=1) { if(n&1) ret=qmut(ret,x,mod); x=qmut(x,x,mod); } return ret; } LL gcd(LL a,LL b) { a=abs(a),b=abs(b); return b? gcd(b,a%b):a; } LL fac[105],tot; bool check(LL a,LL n,LL x,LL t) { LL ret=qpow(a,x,n),last=ret; for(int i=1;i<=t;i++) { ret=qmut(ret,ret,n); if(ret==1&&last!=1&&last!=n-1) return true; last=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++; bool flag=true; if(t>=1 && (x&1)==1) for(int k=0;k<S;k++) { LL a=rand()%(n-1)+1; if(check(a,n,x,t)) { flag=true; break; } flag=false; } if(!flag||n==2) return 0; return true; } LL Pollard_rho(LL x,LL c) { LL i=1,x0=rand()%x,y=x0,k=2; while(1) { i++; x0=(qmut(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 get(LL n) { if(!Miller_Rabin(n)) { fac[tot++]=n; return ; } LL p=n; while(p>=n) p=Pollard_rho(p,rand()%(n-1)+1); get(p); get(n/p); } int main() { int T;scanf("%d",&T); while(T--) { LL n; scanf("%lld",&n); if(!Miller_Rabin(n)) { puts("Prime"); continue; } tot=0; get(n); LL ans=*min_element(fac,fac+tot); printf("%lld ",ans); } }