抄别人的
#include<stdio.h> #include<string.h> #include<algorithm> #include<stdlib.h> #include<time.h> #include<map> using namespace std; typedef long long ll; map<ll,int>m1; ll random(ll n) { return ((double)rand()/RAND_MAX*n+0.5); } ll mult(ll a,ll b,ll c) { ll ans=0; a=a%c; while(b>0) { if(b&1) ans=(ans+a)%c; a=(a+a)%c; b=b>>1; } return ans; } ll quick(ll a,ll b,ll c) { ll ans=1; a=a%c; while(b>0) { if(b&1) ans=mult(ans,a,c); a=mult(a,a,c); b=b>>1; } return ans; } #define TIMES 10 bool witness(ll a,ll n) { ll d =n-1; while(!(d&1)) d>>=1; ll t=quick(a,d,n); while(d!=n-1&&t!=1&&t!=n-1) { t=mult(t,t,n); d<<=1; } return t==n-1||d&1; } bool Miller_Rabin(ll n) { if(n==2) return 1; if(n<2||!(n&1)) return 0; for(int i=1;i<=TIMES;i++) { ll a=random(n-2)+1; if(!witness(a,n)) return 0; } return 1; } ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll pollard_rho(ll n,ll c) { ll x,y,d,i=1,k=2; x=random(n-2)+1; y=x; while(1) { i++; x=(mult(x,x,n)+c)%n; d=gcd(y-x,n); if(d>1&&d<n) return d; if(y==x) return n; if(i==k) { y=x; k<<=1; } } } void find1(ll n,ll c) { if(n==1) return ; if(Miller_Rabin(n)) { m1[n]++; return ; } ll p=n; while(p>=n) p=pollard_rho(p,c--); find1(p,c); find1(n/p,c); } int main() { int t; scanf("%d",&t); while(t--) { ll a; scanf("%lld",&a); m1.clear(); if(Miller_Rabin(a)) printf("Prime "); else { find1(a,12312); map<ll,int>::iterator i=m1.begin(); printf("%lld ",i->first); } } return 0; }