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.

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