一、合数的Miller_Rabin测试：

理论基础：

1. 费马小定理：设p是素数，a是任意整数且a与p互质，则a^(p-1)≡1(mod p).
2. 二次探测定理：设p是素数，x是小于p的正整数，且x^2≡1(modp) , 则x = 1 或 x = p - 1；
   （易证：x^2≡1(mod p)   →  x^2-1≡(mod p)  →  (x+1)(x-1)≡ 0 (mod p)  →  (x+1)=p,(x-1)= 0  →  x = 1 或 x = p - 1）

3. 【中心思想】拉宾-米勒素数测试：设n是奇数，记，q是奇素数，对不被n整除的某个a，如果下述两个条件有一个成立，则n是素数
   ①
   ②对于i=0,1,2……k-1，至少有一个i符合
   （如果n是个合数，则1~n-1之间至少有75%的数可作为n的拉宾-米勒证据，则经过10次测试可将成功率提高至0.999999046）

4. 快速积取模、快速幂取模。

算法过程：

1. n<2时不是素数，n==2是素数，n是偶数时不是素数；（特判）
2. 将n-1分解为 ；
3. 用rand()函数随机取一个正整数a，且1<a<n；
4. 根据上文理论基础3.②从i=0开始检测，共循环k次，若有符合的i，返回false，则证明是合数，循环结束后无i符合，返回true，证明是素数；
5. 反复进行8~10次，可将正确率接近于100%；
6. 多次测试均符合，则可确定n是个素数。
    

 二、pollard_rho大数质因子分解：

 算法过程（转）：

给定：整数n（已知是合数）；

目标：找到一个因子 d | n；

步骤：

1. 固定整数B
2. 选择一个整数k，k是大部分（或者全部）b的乘积满足b≤B；
3. 选择一个随机整数a满足2 ≤ a ≤ n-2
4. 计算 
5. 计算
6. 如果d = 1 或者 d = n，返回步骤 2 ，否则，d就是要找的因子。

 附例题POJ1811（Prime Test ）代码及代码详解：

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <time.h>
using namespace std;
const int S = 10; //随机算法判定次数
// 计算 ret = (a*b)%c a,b,c < 2^63
long long mult_mod(long long a,long long b,long long c)
{
    a %= c;
    b %= c;
    long long ret = 0;
    long long tmp = a;
    while(b)
    {
        if(b & 1)
        {
            ret += tmp;
            if(ret > c)
                ret-= c;//直接取模慢很多
        }
        tmp <<= 1;
        if(tmp > c)
            tmp-= c;
        b >>= 1;
    }
    return ret;
}
// 计算 ret = (a^n)%mod（快速幂）
long long pow_mod(long long a,long long n,long long mod)
{
    long long ret = 1;
    long long temp = a%mod;
    while(n)
    {
        if(n & 1)
            ret = mult_mod(ret,temp,mod);
        temp = mult_mod(temp,temp,mod);
        n >>= 1;
    }
    return ret;
}
//通过a^(n-1)同余1(mod n)来判断是不是素数
// n-1=x*2^t 中间使用二次判断
//是合数返回true，不一定是合数返回false；
bool check(long long a, long long n ,long long x,long long t)
//a为一随机数，n为待检测数也是模，x为（n-1）除去2的倍数后的值，t为n-1所能分解出的2
{
    // n-1=x*2^t;
    long long ret = pow_mod(a,x,n);
    long long last = ret;
    for(int i = 1; i <= t; i++)
    {
        ret = mult_mod(ret,ret,n);
            if(ret== 1&&last!=1&&last!=n-1)
            return true;//合数
        last = ret;
    }
    if(ret != 1)
        return true;
    else
        return false;
}
//**************************************************
// Miller_Rabin 算法
// 是素数返回 true,(可能是伪素数),不是素数返回 false;
//**************************************************
bool Miller_Rabin(long long n)
{
    if( n < 2)
        return false;
    if( n == 2)
        return true;
    if( (n&1) == 0)
        return false;//偶数
    long long x = n - 1;
    long long t = 0;
    while( (x&1)==0 )
    {
        x >>= 1;
        t++;//x能分解出t个2。
    }
    srand(time(NULL));//随机数发生器的初始化函数
    for(int i = 0; i < S; i++)//进行S次检测，减少误差.
    {
        long long a = rand()%(n-1) + 1;//取 1<= a <N的随机数
        if( check(a,n,x,t) )
            return false;
    }
    return true;
}

//**********************************************
// pollard_rho 算法进行质因素分解
//**********************************************
long long factor[100];//质因素分解结果（刚返回时时无序的）
int tol;//质因数的个数 (0~n-1)

long long gcd(long long a,long long b)//欧几里得求最大公约数
{
    long long t;
    while(b)
    {
        t = a;
        a = b;
        b = t%b;
    }
    if(a >= 0)
        return a;
    else
        return -a;
}

//找出一个因子
long long pollard_rho(long long x,long long c)
{
    long long i = 1, k = 2;
    srand(time(NULL));
    long long a = rand()%(x-1) + 1;
    long long y = a;
    while(1)
    {
        i ++;
        a = (mult_mod(a,a,x) + c)%x;
        long long d = gcd(y - a,x);
        if( d != 1 && d != x)
            return d;
        if(y == a)
            return x;
        if(i == k)
        {
            y = a;
            k += k;
        }
    }
}
//对 n 进行素因子分解，存入 factor. k 设置为 107 左右即可
void findfac(long long n,int k)
{
    if(n == 1)
        return;
    if(Miller_Rabin(n))
    {
        factor[tol++] = n;
        return;
    }
    long long p = n;
    int c = k;
    while( p >= n)
        p = pollard_rho(p,c--);//值变化，防止死循环 k
    findfac(p,k);
    findfac(n/p,k);
}
int main()
{
    int T;
    long long n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d",&n);
        if(Miller_Rabin(n))
            printf("Prime\n");
        else
        {
            tol = 0;
            findfac(n,107);
            long long ans = factor[0];
            for(int i = 1; i < tol; i++)
                ans = min(ans,factor[i]);
            printf("%I64d\n",ans);
        }
    }
    return 0;
}