Python Finding Prime Factors

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

Leave a Comment