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.