1.
      #include <cstdlib>
   2.
      #include <cstdio>
   3.
      #include <cstring>
   4.
      #include <iostream>
   5.
      #include <cmath>
   6.

   7.

   8.
      #include "gmp.h"
   9.
      #include <gmpxx.h>
  10.

  11.
      using namespace std;
  12.

  13.

  14.

  15.
      void pollard(mpz_t n, int c)
  16.
      {
  17.
      int k = 1, l = 1;
  18.

  19.
      mpz_t g, t1, t2;
  20.
      mpz_init (g);
  21.
      mpz_init (t1);
  22.
      mpz_init (t2);
  23.

  24.
      mpz_t x, x1, P, a;
  25.
      mpz_init_set_si (a, c);
  26.
      mpz_init_set_si (x, 2);
  27.
      mpz_init_set_si (x1, 2);
  28.

  29.
      mpz_init_set_ui (P, 1);
  30.

  31.

  32.
      while(mpz_cmp_ui(n, 1) != 0)
  33.
      {
  34.
      while(true)
  35.
      {
  36.
      mpz_mul (x, x, x);
  37.
      mpz_add (x, x, a);
  38.
      mpz_mod (x, x, n);
  39.

  40.
      mpz_sub (t1, x1, x);
  41.
      mpz_mul (t2, P, t1);
  42.
      mpz_mod (P, t2, n);
  43.

  44.
      if(--k > 0) continue;
  45.

  46.
      mpz_gcd (g, P, n);
  47.
      if(mpz_cmp_ui(g, 1) != 0) break;
  48.

  49.
      mpz_set(x1, x);
  50.
      k = l;
  51.
      l *= 2;
  52.
      for(int i = 0; i < k; i++)
  53.
      {
  54.
      mpz_mul (x, x, x);
  55.
      mpz_add (x, x, a);
  56.
      mpz_mod (x, x, n);
  57.
      }
  58.
      }
  59.

  60.
      mpz_div (n, n, g);
  61.

  62.
      if (!mpz_probab_prime_p (g, 3))
  63.
      {
  64.
      while(true)
  65.
      {
  66.
      mp_limb_t randomNr;
  67.
      mpn_random (&randomNr, (mp_size_t)1);
  68.
      c = (int)randomNr;
  69.
      if(c != 2 && c != 0) break;
  70.
      }
  71.
      pollard(g, c);
  72.
      }
  73.
      else
  74.
      gmp_printf("%Zd\n", g);
  75.

  76.
      if(mpz_probab_prime_p (n, 3))
  77.
      {
  78.
      gmp_printf("%Zd\n", n);
  79.
      break;
  80.
      }
  81.
      }
  82.

  83.
      mpz_clear (g);
  84.
      mpz_clear (P);
  85.
      mpz_clear (t2);
  86.
      mpz_clear (t1);
  87.
      mpz_clear (a);
  88.
      mpz_clear (x1);
  89.
      mpz_clear (x);
  90.
      }
  91.

  92.
      int main (int argc, char *argv[])
  93.
      {
  94.

  95.
      mpz_t tt;
  96.
      mpz_init(tt);
  97.
      while(gmp_scanf("%Zd", tt))
  98.
      {
  99.
      pollard(tt, 1);
 100.
      printf("\n");
 101.
      }
 102.

 103.

 104.
      return 0;
 105.
      }
 106.