/*
	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();
}