Any integer n can be written in the form
$ n = p_1^{k_1}p_2^{k_2} … p_r^{k_r} $,
where the powers $ k_1, k_2, …,k_r $ are integers and
$ p_1, p_2, …, p_r$ are primes.
Now I am interested in whether there are quicker methods for finding the powers, other than trial and error? For example, if I wanted to write a large number such as 567 788 in the above form, and it looked something like this:
$567 788 = p_1^{k_1}p_2^{k_2}p_3^{k_3} $
what methods could could be applied, to determine the relevant prime factors $ p$, and by what power $k$ to raise each prime $p$?
Best Answer
To find the powers, you must iterate, but there are efficient ways of doing it.
For starters, each time you find a prime factor $p$, factor it out of $n$ before looking for new factors. For your example:
$$567788=2*283894=2*2*141947$$
We factor $2$ out until it doesn't come out anymore, then look for the next factor. 3,5,7,11 are not factors, 13 is, so
$$=2*2*13*10919$$
13 does not divide again, keep trying factors until finding 61 works
$$=2*2*13*61*179$$
We know that 179 is prime without having to try any other prime factors because we already know it cannot be divisible by anything less than the last prime factor we found (61) which is more than $\sqrt{179}$. Notice we did not need to try dividing by any number larger than 61, which is a good deal less than $\sqrt{567788}\approx750$.
There are certainly other ways of doing this but this is both simple to understand and implement and saves you a lot of computation from your previous method.