Rho.cpp

/*
  The implementation of Rho Method with C++
  varified with NTL_1_A
  
  http://joisino.hatenablog.com/entry/2017/08/03/210000
  
  Copyright (c) 2017 joisino
  Released under the MIT license
  http://opensource.org/licenses/mit-license.php
 */

#include <bits/stdc++.h>

using namespace std;

struct Miller{
  const vector<long long> v = { 2 , 7 , 61 }; // < 4,759,123,141
  // x^k (mod m)
  long long modpow( long long x, long long k, long long m ){
    long long res = 1;
    while( k ){
      if( k & 1 ){
        res = res * x % m;
      }
      k /= 2;
      x = x * x % m;
    }
    return res;
  }
  // check if n is prime
  bool check( long long n ){
    if( n < 2 ){
      return false;
    }
    long long d = n - 1;
    long long s = 0;
    while( d % 2 == 0 ){
      d /= 2;
      s++;
    }
    for( long long a : v ){
      if( a == n ){
        return true;
      }
      if( modpow( a , d , n ) != 1 ){
        bool ok = true;
        for( long long r = 0; r < s; r++ ){
          if( modpow( a, d * (1LL << r), n ) == n-1 ){
            ok = false;
            break;
          }
        }
        if( ok ){
          return false;
        }
      }
    }
    return true;
  }
};

struct Rho{
  mt19937 mt;
  Miller miller;
  long long c;
  Rho(){
    mt.seed( clock() );
  }
  inline long long f( long long x, long long n ){
    return ( x * x + c ) % n;
  }
  long long check( long long n ){
    if( n == 4 ){
      return 2;
    }
    c = mt() % n;
    long long x = mt() % n;
    long long y = x;
    long long d = 1;
    while( d == 1 ){
      x = f(x, n);
      y = f(f(y,n),n);
      d = __gcd( abs(x-y), n );
    }
    if( d == n ){
      return -1;
    }
    return d;
  }
  vector<long long> factor( long long n ){
    if( n <= 1 ){
      return {};
    }
    if( miller.check( n ) ){
      return { n };
    }
    long long res = -1;
    while( res == -1 ){
      res = check( n );
    }
    vector<long long> fa = factor( res );
    vector<long long> fb = factor( n / res );
    fa.insert( fa.end() , fb.begin(), fb.end() );
    return fa;
  }
};

Rho rho;

int main(){

  int n;
  scanf( "%d" , &n );
  vector<long long> ans = rho.factor( n );
  sort( ans.begin(), ans.end() );
  printf( "%d:" , n );
  for( long long x: ans ){
    printf( " %lld" , x );
  }
  printf( "\n" );

  // bench
  /*
  const int MAX_N = 1000000000;
  const int loop = 100000;
  mt19937 mt( 1234 );
  for( int i = 0; i < loop; i++ ){
    int n = mt() % MAX_N;
    rho.factor( n );
  }
  */
  

  return 0;
}