|
|
Posted on 2011-09-02 11:12 成幸毅 阅读(455) 评论(0) 编辑 收藏 引用
 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 1100;
typedef __int64 bigint;
bigint gcd(bigint A,bigint B)
   {
 while(B)
  {
bigint C = A%B;
A = B;
B = C;
 }
return A;
 }
bigint product_mod(bigint A,bigint B,bigint C)
{
bigint R = 0,D = A;
while(B)
{
if(B&1)
{
R = (R+D);
if(R>C) R -= C;
}
D += D;
if(D>C) D -= C;
B >>= 1;
}
return R;
}
bigint power_mod(bigint A,bigint B,bigint C)
{
bigint R = 1,D = A;
while(B)
{
if(B&1) R = product_mod(R,D,C);
D = product_mod(D,D,C);
B >>= 1;
}
return R;
}
int pri[] = {2,3,5,7,11,13,17,19,23,29};
bool Miller_Rabin(bigint n)
{
if(n<2) return false;
if(n==2) return true;
if(!(n&1)) return false;
bigint k = 0,i,j,m,a;
m = n-1;
while(!(m&1)) m = (m>>1),k++;
for(i=0;i<10;i++)
{
if(pri[i]>=n) return true;
a = power_mod(pri[i],m,n);
if(a==1) continue;
for(j=0;j<k;j++)
{
if(a==n-1) break;
a = product_mod(a,a,n);
}
if(j==k) return false;
}
return true;
}
bigint pollard_rho(bigint C,bigint N)
{
bigint I,X,Y,K,D;
I = 1;
X=Y=rand()%N;
K = 2;
do{
I++;
D = gcd(N+Y-X,N);
if(D>1&&D<N) return D;
if(I==K) Y=X,K<<=1;
X=(product_mod(X,X,N)+N-C)%N;
}while(Y!=X);
return N;
}
bigint allFactor[maxn];
int fn;
void rho(bigint N)
{
if(Miller_Rabin(N))
{
allFactor[++fn]=N;
return ;
}
bigint T = N;
while(T>=N) T = pollard_rho(rand()%(N-1)+1,N);
rho(T);
rho(N/T);
}
int main()
{
bigint n;
while(true)
{
scanf("%I64d",&n);
if(n<=0) break;
if(Miller_Rabin(n)) printf(" %I64d\n",n);
else
{
fn=0;
rho(n);
sort(allFactor+1,allFactor+fn+1);
for(int i=1;i<=fn;i++)
{
printf(" %I64d\n",allFactor[i]);
}
}
cout<<endl;
}
return 0;
}
|