Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Are the prime factors known ? –  Amr Jan 21 '13 at 11:00
    
I haven't yet worked out the prime factors of this number. In fact, it could be divisible by any prime $\leq \sqrt{567788}$... So, actually, I'd be interested in learning methods of determining prime factors of large numbers too. –  Seraphina Jan 21 '13 at 11:14
3  
Books have been written on methods for factoring integers. Some of the methods depend on very advanced mathematics. Here are a few keyphrases you could search for: Pollard rho; Pollard $p-1$; quadratic sieve; elliptic curve factorization method; SQUFOF; number field sieve. –  Gerry Myerson Jan 21 '13 at 11:23
1  
I think you can check effective factoring techniques. As far as I know (and I don't much about this topic) , determining the prime factors of a large number is an important problem that is related to cryptography. –  Amr Jan 21 '13 at 11:24

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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