/*
This program reads large number from file input.txt and outputs
factorization of it. Program uses Pollard algorithm.
Compile with -lgmp -lgmpxx options.
*/
#include
#include
#include
#include
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();
}