Project Euler 3 - Why does this method work?

Question

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

I solved this problem on Project Euler my own way, which was slow, and then I found this solution on someone's github account. I can't figure out why it works. Why are a number of factors removed, equal to an index? Any insight?

def Euler3(n=600851475143):
    for i in range(2,100000):
        while n % i == 0:
            n //= i
            if n == 1 or n == i:
                return i

Answer 1

This function works by finding successive factors of its input. The first factor it finds will necessarily be prime. After a prime factor is found, it is divided out of the original number and the process continues. By the time we've divided them all out (leaving 1, or the current factor (i)) we've got the last (largest) one.

Let's add some tracing code here:

def Euler3(n=600851475143):
    for i in range(2,100000):
        while n % i == 0:
            n //= i
            print("Yay, %d is a factor, now we should test %d" % (i, n))
            if n == 1 or n == i:
                return i

Euler3()

The output of this is:

$ python factor.py
Yay, 71 is a factor, now we should test 8462696833
Yay, 839 is a factor, now we should test 10086647
Yay, 1471 is a factor, now we should test 6857
Yay, 6857 is a factor, now we should test 1

It is true that for a general solution, the top of the range should have been the square root of n, but for python, calling math.sqrt returns a floating point number, so I think the original programmer was taking a lazy shortcut. The solution will not work in general, but it was good enough for the Euler project.

But the rest of the algorithm is sound.

Answer 2

Consider how it solves for n=20:

iteration i=2
  while true (20 % 2 == 0)
    n = n//2 = 20//2 = 10
    if (n == 1 or n == 2) false
  while true (10 % 2 == 0)
    n = n//2 = 10//2 = 5
    if (n == 1 or n == 2) false
  while false (5 % 2 == 0)
iteration i = 3
  while false (5 % 3 == 0)
iteration i = 4 
  while false (5 % 4 == 0)
iteration i = 5
  while true (5 % 5 == 0)
    n = n//5 = 5//5 = 1
    if (n == 1 or n == 5) true
      return i, which is 5, which is the largest prime factor of 20

It is just removing factors, and since it already removes multiples of prime factors (the while loop), many values of i are really just wasted effort. The only values of i that have any chance of doing something within the loop are prime values of i. The n==i test covers the case of numbers like 25 that are squares of a prime number. The range seems to limited though. It would not give the correct answer for 2 * (the next largest prime after 100,000.