I one of the programming contest, I was asked to list all the factors of a given number. As usual, I checked for divisibility till $\sqrt n$. However, my solution timed out for a number in the order of $10^{10}$.
I was then recommended to learn about Pollard Rho. I have sort of got the essence of this algorithm by reading this article.
It seems Pollard Rho algorithm can only be used to get just 2 factors and that too is sort of random.
So, how could I use Pollard Rho to obtain all the factors of the given integer? Or is there another elegant algorithm which will help me get all the factors in less than $\sqrt n$?
Best Answer
Given a number $n$ and a prime factor $p$ of that number, i.e $p|n$, the other factors of $n$ are also factors of $\frac{n}{p}$, so if you have an algorithm for finding a prime factor of a number, you can just continue by applying that to $\frac{n}{p}$. If your algorithm gives you a factor $m$ that might not be prime (and I don't remember if Pollard Rho does), you'll of course also have to factor that.