随机拆分，简直机智。

关于过程可以看http://wenku.baidu.com/link?url=JPlP8watmyGVDdjgiLpcytC0lazh4Leg3s53WIx1_Pp_Y6DJTC8QkZZqmiDIxvgFePUzFJ1KF1G5xVVAoUZpxdw9GN-S46eVeiJ6Q-zXdei

看完后，觉得随机生成数然后和n计算gcd，可以将随机的次数根号一下。思想很叼。

对于里面说的birthday trick，在执行次数上我怎么看都只能减一半。只是把平均分布，变成了靠近0的的分布。

不过怎么说，这个好像是大家都公认比较靠谱的。 所以，我就勉强相信了。

/*****************************大整数拆分模板（long long范围内）调用Divide(n,222);返回的结果在divsor中，因子最小值为dmi注意：复杂度为n^(1/4),多次调用初始化dcnt,dmi*****************************/#define INF 1e18long long divsor[100];int dcnt=0;long long dmi=INF;//输入一个long long 范围内的素数，是素数返回true，否则返回false。定义检测次数TIMES,错误率为(1/4)^TIMES#define TIMES 10long long GetRandom(long long n){    //cout<
     
      <
      
       >=1;        a = (a+a)%mod;    }    return msum;}long long Quk_Mul(long long a,long long b,long long mod){    long long qsum=1;    while(b)    {        if(b&1) qsum=Mod_Mul(qsum,a,mod);        b>>=1;        a=Mod_Mul(a,a,mod);    }    return qsum;}bool Miller_Rabin(long long n){    if(n==2||n==3||n==5||n==7||n==11) return true;    if(n==1||n%2==0||n%3==0||n%5==0||n%7==0||n%11==0) return false;    int div2=0;    long long tn=n-1;    while( !(tn%2) )    {        div2++;        tn/=2;    }    for(int tt=0;tt
       
        =dn) dtmp = pollard_rho(dtmp,dk--);//随机寻找dn的因子，dtmp    Divide(dtmp, dk);    Divide(dn/dtmp,dk);}/*int main() {    int T;    cin>>T;    while(T--)    {        long long n;        cin>>n;        if( Miller_Rabin(n) ) printf("Prime\n");        else        {            dmi=INF;            dcnt=0;            Divide(n,222);            cout<
        
         <