Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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
share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.