4
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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