# Algorithm for generation of Canonical represented integers [closed]

Is there a way to get canonical representation of an integer by algorithm? I can get primes, but I don't know how to represent, for example, 1000 as 2^3×5^3. How can I compute the power of each prime number?

• en.wikipedia.org/wiki/Integer_factorization – D.W. Sep 9 '14 at 17:47
• @D.W. there are around 15 algorithms. I don't know which one could give canonical representation. Do you? – cassandrad Sep 9 '14 at 18:05
• Not sure what "canonical" means in this case. But somehow you were able (by hand) to figure out $1000 = 2^3 \times 5^3$. Figure out what you did by hand. That's the algorithm. – Wandering Logic Sep 9 '14 at 21:06

What you're calling the canonical form is a consequence of the fundamental theorem of arithmetic which states that every integer $n>1$ can be uniquely expressed (up to order) as a product, $$n = p_1^{a_1}\ p_2^{a_2}\ \dots \ p_k^{a_k}$$ where the $p_i$ are distinct primes. From a theoretical standpoint, this is particularly interesting since it's currently unknown whether or not there is an efficient algorithm to solve this problem (namely, an algorithm that runs in time polynomial in the number of digits of $n$). Nobody has come up with an efficient algorithm for factorization, but, unlike a lot of known "hard" problems, like the traveling salesman problem, no one has provided a proof that factorization must be hard. While @FrankW's suggested algorithm can be slightly improved, as far as anyone presently knows there's no really efficient solution.