Pollard "p-1"方法 分解合数的因素；

/*
 Pollard "p-1"方法
 （1）.选取一个可被许多素数的幂次整除的正整数k；例如k=LCM（1，2，……B）
 （2）指数。计算ak=a^k mod n;
 （3）计算最大公因子，计算d=gcd（ak-1，n）
 （4）找到因子？若1<d<n,则d为n 的非平凡因子。然后尽心步骤（6）
 （5）重新开始？若d不是n 的平凡因子，且还想再进行一次实验的话则返回（2）
        重新选择a和k,再进行上述步骤，否则执行步骤（6）
（6）退出。
 */

#includes<iostream>

using namespace std;
  long long factoring(long long n)
 {
      long long a,k=840,d,ak;
      int t=0;
      srand((unsigned)time(NULL));
      a=rand()%n;
      if(a<2)a=a+2;
       a=2;
       while(1)
       {
         long long i;
         ak=1;
         for(i=0;i<k;i++)
                ak=(ak*a)%n;
         if(ak==0)ak=n;
         d=gcd(n,ak-1);
         if(d<n&&d>1&&n%d==0)
         {

             return d;
          }
          a=rand()%n;
          if(a<2)a=a+2;
      }
 }
int main()
{
   long long n;
   int i;
   cin>>n;
   cout<<factoring(n,fa,number)<<endl;
    return 0;
}