poj 1811 (素数判定+质因数分解) - c++编程基础

题意：给定一个64位整数，问是否为质数，如果不是，则输出其最小因子。

分析：经典题数学题，给的数太大，普通方法肯定超时，就在网上找了这个算法

miller_rabbin素数判定。若不是，则pollard_rho分解质因子，找到最小即可。

Miller-rabin算法是一个用来快速判断一个正整数是否为素数的算法。它利用了费马小定理，即：如果p是质数，且a，p互质，那么a^(p-1) mod p恒等于1。也就是对于所有小于p的正整数a来说都应该复合a^(p-1) mod p恒等于1。那么根据逆否命题，对于一个p，我们只要举出一个a（a

但是每次尝试过程中还做了一个优化操作，以提高用少量的a检测出p不是素数的概率。这个优化叫做二次探测。它是根据一个定理：如果p是一个素数，那么对于x(0

pollard-rho

这是一个用来快速对整数进行质因数分解的算法，需要与Miller-rabin共同使用。求n的质因子的基本过程是，先判断n是否为素数，如果不是则按照一个伪随机数生成过程来生成随机数序列，对于每个生成的随机数判断与n是否互质，如果互质则尝试下一个随机数。如果不互质则将其公因子记作p，递归求解p和n/p的因子。如果n是素数则直接返回n为其素因子。

#include  
#include  
#include  
#include  
typedef __int64 LL;  
const int S=20;//随机算法判定次数，S越大，判错概率越小  
  
//***************Miller_Rabin 算法进行素数测试***************  
LL mult_mod(LL a,LL x,LL n)//返回(a*x) mod n,a,x,n<2^63  
{  
    a%=n;x%=n;  
    LL ret=0;  
    while(x)  
    {  
        if(x&1){ret+=a;if(ret>=n)ret-=n;}  
        a<<=1;  
        if(a>=n)a-=n;  
        x>>=1;  
    }  
    return ret;  
}  
LL pow_mod(LL a,LL x,LL n)//返回a^x mod n  
{  
    if(x==1)return a%n;  
    int bit[70],k=0;  
    while(x)  
    {  
        bit[k++]=(x&1 1:0);  
        x>>=1;  
    }  
    LL ret=1;  
    for(--k;k>=0;k--)  
    {  
       ret=mult_mod(ret,ret,n);  
       if(bit[k])ret=mult_mod(ret,a,n);  
    }  
    return ret;  
}  
bool judge(LL a,LL n,LL x,LL t)//以a为基，n-1=x*2^t，检验n是不是合数  
{  
    LL ret=pow_mod(a,x,n),flag=ret;  
    for(LL i=1;i<=t;i++)  
    {  
        ret=mult_mod(ret,ret,n);  
        if(ret==1&&flag!=1&&flag!=n-1)return true;  
        flag=ret;  
    }  
    if(ret!=1)return true;  
    return false;  
}  
bool Miller_Rabin(LL n)  
{  
    if(n==2||n==5||n==7||n==11)return true;  
    if(n%2==0||n%5==0||n%7==0||n%11==0)return false;  
    LL x=n-1,t=0;  
    while((x&1)==0)x>




>=1,t++;  
    bool flag=true;  
    if(t>=1&&(x&1)==1)  
    {  
        for(int i=1;i<=S;i++)  
        {  
            LL a=rand()%(n-1)+1;  
            if(judge(a,n,x,t)){flag=true;break;}  
            flag=false;  
        }  
    }  
    if(flag)return false;  
    else return true;  
}  
//*******pollard_rho 算法进行质因数分解*****************  
LL factor[100];//质因子  
int tot;//质因子个数  
LL gcd(LL a,LL b)  
{  
    if (a==0) return 1;  
    if (a<0) return gcd(-a,b);  
    while (b)  
    {  
        LL t=a%b; a=b; b=t;  
    }  
    return a;  
}  
LL Pollard_rho(LL x,LL c)  
{  
    LL i=1,x0=rand()%x,y=x0,k=2;  
    while (1)  
    {  
        i++;  
        x0=(mult_mod(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 find_factor(LL n) //递归进行质因数分解N  
{            
    if (Miller_Rabin(n))  
    {  
        factor[tot++] = n;return;          
    }  
    LL p=n;  
    while (p>=n) p=Pollard_rho(p,rand() % (n-1) +1);  
    find_factor(p);  
    find_factor(n/p);  
}  
int main()  
{  
    int t;  
    LL n;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%I64d",&n);  
        if(Miller_Rabin(n))  
            printf("Prime\n");  
        else  
        {  
            tot=0;  
            find_factor(n);  
            LL minfac=factor[0];  
            for(int i=1;ifactor[i])  
                    minfac=factor[i];  
            printf("%I64d\n",minfac);  
        }  
    }  
    return 0;  
}