#include<RandomNumber.h>
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
void Pollard(int n)
{
RandomNumber rnd;
int i=1;
int x=rnd.Random(n);
int y=x;
int k=2;
while(true)
{
i++;
x=(x*x-1)%n;
int d=gcd(y-x,n);
if((d>1)&&(d<n)) cout<<d<<endl;
if(i==k){
y=x;
k*2;}
}
}
void main
{
int n;
cout<<请输入一个数字<<endl;
cin>>n;
int result=Pollard(n);
cout<<result<<endl;
}
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
void Pollard(int n)
{
RandomNumber rnd;
int i=1;
int x=rnd.Random(n);
int y=x;
int k=2;
while(true)
{
i++;
x=(x*x-1)%n;
int d=gcd(y-x,n);
if((d>1)&&(d<n)) cout<<d<<endl;
if(i==k){
y=x;
k*2;}
}
}
void main
{
int n;
cout<<请输入一个数字<<endl;
cin>>n;
int result=Pollard(n);
cout<<result<<endl;
}