Largest Prime Factor

Question

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

Answer 1

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 http://stackoverflow.com/questions/1504717/python-vs-is-comparing-strings-is-fails-sometimes-why