# Largest Prime Factor

I'm trying to learn Python by working my way through problems on the Project Euler website. I managed to solve problem #3, which is

What is the largest prime factor of the number 600851475143 ?

However, my code looks horrible. I'd really appreciate some advice from experienced Python programmers.

import math
import unittest

def largestPrime(n, factor):
"""
Find the largest prime factor of n
"""

def divide(m, factor):
"""
Divide an integer by a factor as many times as possible
"""
if m % factor is 0 :
return divide(m / factor, factor)
else :
return m

def isPrime(m):
"""
Determine whether an integer is prime
"""
if m is 2 :
return True
else :
for i in range(2, int(math.floor(math.sqrt(m))) + 1):
if m % i is 0 :
return False
return True

# Because there is at most one prime factor greater than sqrt(n),
# make this an upper limit for the search
limit = math.floor(math.sqrt(n))

if factor <= int(limit):
if isPrime(factor) and n % factor is 0:
n = divide(n, factor)
if n is 1:
return factor
else:
return largestPrime(n, factor + 2)
else:
return largestPrime(n, factor + 2)
return n


Some thoughts:

Divide function has been implemented recursively. In general, recursive implementations provide clarity of thought despite being inefficient. But in this case, it just makes the code cumbersome.

while m % factor == 0:
m /= factor
return m


should do the job.

A lot of computational work is done by isPrime which is unnecessary. Eg: when factor 15 is being considered, the original n would've been already Divided by 3 and 5. So, if factor is not a prime then n%factor will not be 0.

So, the following should do:

import math
def largestPF(n):
limit = int(math.sqrt(n)) + 1
for factor in xrange(2, limit+1):
while n % factor == 0:
n /= factor
if n == 1:
return factor
return n


You can of course, include the 'run through factors in steps of 2' heuristic if you want.

PS: Be careful with the is statement for verifying equality. It might lead to unexpected behaviour. Check out https://stackoverflow.com/questions/1504717/python-vs-is-comparing-strings-is-fails-sometimes-why