# 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?

## closed as unclear what you're asking by D.W.♦, Kyle Jones, David Richerby, Wandering Logic, JuhoSep 12 '14 at 7:41

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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.