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:
The prime-numbers used in miller-rabin needs to be more, to check for higher constraints.
Overflow (maybe)
I would like to know
How to make my code more faster
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.