0
$\begingroup$

This question on math.stackexchange details an algorithm that can be used to find the largest prime factor of a number. I used it to solve Project Euler #3. Here's a short description of the algorithm:

Detailed Algorithm description:

You can do this by keeping three variables:

The number you are trying to factor (A)
A current divisor store (B)
A largest divisor store (C)

Initially, let (A) be the number you are interested in - in this case, it is 600851475143. Then let (B) be 2. Have a conditional that checks if (A) is divisible by (B). If it is divisible, divide (A) by (B), set (C) equal to (B), reset (B) to 2, and go back to checking if (A) is divisible by (B). Else, if (A) is not divisible by (B), increment (B) by +1 and then check if (A) is divisible by (B). Run the loop until (A) is 1. The (C) you return will be the largest prime divisor of 600851475143.

My implementation of the algorithm works and I was able to answer the question correctly.

Please explain how it is guaranteed that the resultant (C) will be the largest prime factor of the number and not just the largest factor.

Any axioms or proofs related to prime numbers etc that can be referenced to explain how this method of trial division produces the largest prime factor of a given number will much appreciated.

$\endgroup$
0
$\begingroup$

Write your number as $2^a\times3^b\times5^c\times7^d\times11^e...$

Note that you store the previous largest divisor in $C$.

Divisibility by $C$ would have no affect if you keep eliminating these lower primes. Once all lower divisors are eliminated you would have, say, $p^{\alpha}$.

Next dividing by it would store it in $C$. Then you successively reduce your number to 1.

Example: Let the number be 105. Note that writing is like this is to be in your mind.$$105=3^1\times5^1\times7^1 things would be like this in runtime :

We have to divide by all lower primes. not divisible by 2. C not storing anything(mathematically, technically there will be junk value)

Next prime is 3. Divisible by it. $C=3$. Now there is no need of this 3. eliminate it. new number $= 105/3=35$

But this may still contain another factor of 3. let's try. not divisible. So set next prime 5. Repeat above procedure till C stores 7 and the number becomes 1.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The first sentence doesn't make sense to me. How do I write 600851475143 using that format? And what do the variables a, b, c, d and e represent in that context? $\endgroup$ – James Nicholson Apr 14 '14 at 18:16
  • $\begingroup$ Its prime factorization. You are actually taking increasing powers of prime from your number. $\endgroup$ – evil999man Apr 15 '14 at 4:52
  • $\begingroup$ Can you type out an explained example of this using, say, 105 as the number for which you're trying to find the largest prime factor? $\endgroup$ – James Nicholson Apr 15 '14 at 20:40
  • $\begingroup$ lemme edit${}{}$ $\endgroup$ – evil999man Apr 16 '14 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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