采用PallardRho算法实现大因数分解

#include<iostream> #include<math.h> #include<ctime> using namespace std; #define RUN 100 extern long Randomi(long a,long b); extern long Extend_EuleGCD(long a,long b); bool IsPrime( long d) //这是规模变小后的再来判断，所以效率应该会低些 { for(int i=2;i<(int)sqrt((double)d)+1;i++) if(0==d%i) return false; return true; } long Pallard_RHO(long n) { long i=1; long x=Randomi(0,n-1); long y=x; long k=2; long d; int countRun=(int)pow(n,0.25)+1; //记循环的次数,次数过后,如果没有退出循环，重新再来选择随机种子 while(true&&countRun!=0) { srand((unsigned)time(NULL)); countRun--; x=x*x-1; x=x%n; //invalidate variable x long xy=abs(x-y); d=Extend_EuleGCD(xy,n); if(d!=1&&d!=n) { return d; } if(i==k) //count,if i is even number,then save the value of x in y { y=x; k=k*2; } } } void Print( long d) { if(IsPrime(d)&&d!=1) cout<<d<<" "; } int main() { long n; cout<<"Enter the number(Composite) you want to factorize:"<<endl; cin>>n; cout<<"the number is compositing……"<<endl; if(IsPrime(n)) { cout<<n<<" is Prime!"<<endl; return 0; } long factor=1; for(int i=0;i<RUN;i++) { while(n!=factor) //factor应该肯定在执行过程中为素数 { factor=Pallard_RHO(n); while(!IsPrime(factor)) { factor=Pallard_RHO(factor); } Print(factor); n=n/factor; if(IsPrime(n)) { cout<<n<<endl; break; } } } return 0; }