0
$\begingroup$

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?

$\endgroup$

closed as unclear what you're asking by D.W., Kyle Jones, David Richerby, Wandering Logic, Juho Sep 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.

  • $\begingroup$ en.wikipedia.org/wiki/Integer_factorization $\endgroup$ – D.W. Sep 9 '14 at 17:47
  • $\begingroup$ @D.W. there are around 15 algorithms. I don't know which one could give canonical representation. Do you? $\endgroup$ – cassandrad Sep 9 '14 at 18:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Wandering Logic Sep 9 '14 at 21:06
4
$\begingroup$

The simplest algorithm to do this is to divide repeatedly by the prime, until the division no longer yields an integer.

$\endgroup$
  • $\begingroup$ Yes, but this algorithm doesn't seem to be efficient. Do we have more efficient solutions? $\endgroup$ – cassandrad Sep 9 '14 at 17:44
  • $\begingroup$ @cassandradied It depends on how big the number is which you start with as you can stop when the test divisor is more than the square root of the dividend. For example the JavaScript at se16.info/js/factor.htm does this and is fairly fast for reasonable numbers (say up to 10^12). There are faster methods and methods which handle larger numbers, such as the Java applet at alpertron.com.ar/ECM.HTM $\endgroup$ – Henry Sep 9 '14 at 19:40
  • $\begingroup$ @cassandradied this algorithm is much more efficient than any general method for finding prime divisors. I don't see why you oppose it. $\endgroup$ – bbejot Sep 9 '14 at 20:13
  • $\begingroup$ @Henry could you link me the faster methods? I'm looking for solution for the numbers with 100 digits and more. There is no problem in memory or implementation. I need less complex solution in terms of algorithmic complexity. Could you imagine dividing all numbers from 1 to 100-digit-number with all primes in that range? I will mark your answer if no one will give others anyway tomorrow. $\endgroup$ – cassandrad Sep 9 '14 at 20:16
  • 1
    $\begingroup$ @cassandradied that's what I'm saying. once you have the prime divisors of a number, then calculating how many times each prime divides the number (what FrankW is solving) is computationally trivial. Finding the prime divisors, which you've stated you can already do, is the hard part. $\endgroup$ – bbejot Sep 9 '14 at 20:29
3
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.