Python Finding Prime Factors

Question

Two part question:

1) Trying to determine the largest prime factor of 600851475143, I found this program online that seems to work. The problem is, I'm having a hard time figuring out how it works exactly, though I understand the basics of what the program is doing. Also, I'd like if you could shed some light on any method you may know of finding prime factors, perhaps without testing every number, and how your method works.

Here's the code that I found online for prime factorization [NOTE: This code is incorrect. See Stefan's answer below for better code.]:

n = 600851475143
i = 2
while i * i < n:
     while n % i == 0:
         n = n / i
     i = i + 1

print (n)

#takes about ~0.01secs

2) Why is that code so much faster than this code, which is just to test the speed and has no real purpose other than that?

i = 1
while i < 100:
    i += 1
#takes about ~3secs

Answer 1

This question was the first link that popped up when I googled "python prime factorization". As pointed out by @quangpn88, this algorithm is wrong (!) for perfect squares such as n = 4, 9, 16, ... However, @quangpn88's fix does not work either, since it will yield incorrect results if the largest prime factor occurs 3 or more times, e.g., n = 2*2*2 = 8 or n = 2*3*3*3 = 54.

I believe a correct, brute-force algorithm in Python is:

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

Don't use this in performance code, but it's OK for quick tests with moderately large numbers:

In [1]: %timeit largest_prime_factor(600851475143)
1000 loops, best of 3: 388 μs per loop

If the complete prime factorization is sought, this is the brute-force algorithm:

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors