关键算法：

Miller-Rabbin判断素数。http://www.dxmtb.com/blog/miller-rabbin/

Pollard-Rho找出整数的任意一个因子。http://www.dxmtb.com/blog/pollard-rho/

先跟着他讲的写了一遍。太神了。

找因子的时候因为找出来的是任意一个。所以还要继续二分直到找到最小的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int S=30,C=240;
typedef long long ll;
ll An;
ll mul(ll a,ll b,ll c){
    ll r;   for(r=0;b;a=(a<<1)%c,b>>=1) if(b&1) r=(r+a)%c;  return r;
}ll pow(ll a,ll b,ll c){
    ll r;   for(r=1;b;a=mul(a,a,c),b>>=1)   if(b&1) r=mul(r,a,c);    return r;
}int miller_rabbin(ll n){
    if(n==2)    return 1;   if(n<2||!(n&1)) return 0;
    int t=0;    ll a,x,y,u=n-1;
    while(!(u&1))   t++,    u>>=1;
    for(int i=0;i<S;i++){
        a=rand()%(n-1)+1;
        x=pow(a,u,n);
        for(int j=0;j<t;j++){
            y=mul(x,x,n);
            if(y==1&&x!=1&&x!=n-1)  return 0;
            x=y;
        }if(x!=1)   return 0;
    }return 1;
}ll gcd(ll a,ll b){
    return (!b)?a:gcd(b,a%b);
}ll pollard_rho(ll n,ll c){
    ll x,y,d,i=1,k=2;
    x=rand()%(n-1)+1;y=x;
    while(++i){
        x=(mul(x,x,n)+c)%n; 
        d=gcd(y-x,n);
        if(1<d&&d<n)    return d;
        if(x==y)    return n;
        if(i==k)    y=x,k<<=1;
    }
}void find(ll n,ll c){
    ll m;
    if(n==1)    return;
    if(miller_rabbin(n)){ An=min(An,n);   return;}
    m=n;    while(m==n) m=pollard_rho(n,c--);
    find(m,c);  find(n/m,c);
}int main(){
    int tc; scanf("%d",&tc);    ll n;
    while(tc--){
        scanf("%lld",&n);
        if(miller_rabbin(n))    printf("Prime\n");
        else{   An=1ll<<60ll;   find(n,1LL*C);  printf("%lld\n",An);}
    }return 0;
}

• 相关文章