I have been trying to solve this question for a very long time: https://www.spoj.com/problems/FACT2/ (29 digits), I have already solved the task with smaller constraints (19 digits).

My implementation

Prime_factorization (num):
    prime_factor = pollard_rho (num)
    while (miller_rabin( prime_factor) != true):
        prime_factor = miller_rabin( prime_factor )
    while num%prime_factor == 0:
        num /= prime_factor

Here pollard-rho guesses a suitable prime factor and miller-rabin checks if returned factor is a prime.

My implementation (Code, C++) : https://github.com/forgotter/Snippets/blob/master/prime_factorization.cpp

Bugs in current implementation:

1. The prime-numbers used in miller-rabin needs to be more, to check for higher constraints.

2. Overflow (maybe)

I would like to know

1. How to make my code more faster

2. How to handle inputs larger than 10^18 (should I write one library for myself which can perform basic operations (+,-,*,/) on string.

Also, if someone can provide with a good tutorial on quadratic sieve. And with implementation would be too good to have.

Thanks for reading.

P.S: This is my first blog post. Please ignore minor mistakes.