/*
       This program reads large number from file input.txt and outputs
       factorization of it. Program uses Pollard algorithm.
       Compile with -lgmp -lgmpxx options.
*/

#include <iostream>
#include <fstream>
#include <gmpxx.h>
#include <gmp.h>
using namespace std;

const int REPS_MAX = 20;
gmp_randclass randget(gmp_randinit_default);

mpz_class div(mpz_class N)
{
       mpz_class c = randget.get_z_range(N);
       mpz_class x = randget.get_z_range(N);
       mpz_class y = x;
       mpz_class divisor;
       mpz_class x_y;
       mpz_class ONE = 1;

       // check divisibility by 2
       if ((N % 2) == 0) return 2;

       do {
               x = ((x * x) % N) + (c % N);
               y = ((y * y) % N) + (c % N);
               y = ((y * y) % N) + (c % N);
               x_y = x - y;
               mpz_gcd(divisor.get_mpz_t(), x_y.get_mpz_t(), N.get_mpz_t());
       } while (divisor == 1);

       return divisor;
}

void factor(mpz_class N)
{
       if (N == 1) return;
       if (mpz_probab_prime_p(N.get_mpz_t(), REPS_MAX))
       {
               cout << N << endl;
               return;
       }

       mpz_class divisor = div(N);
       factor(divisor);
       factor(N / divisor);
}
int main()
{
       ifstream infile("input.txt", ios::in);
       mpz_class N;
       infile >> N;

       factor(N);

       infile.close();
}