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.