gistfile1.py

"""Project Euler: Problem 3"""

def largest_prime_factor(num):
    """Determines the largest prime factor of the given number"""
    def divide_out_multiples(ix, num):
        """Removes swathes of multiples at a time. If two is a multiple,
           we remove any even factors and return the result.
        """
        while num % ix == 0:
            num /= ix
        return num

    # Get rid of any even factors
    num = divide_out_multiples(2, num)
    # Initialize looping on three and increment index ix by two each loop
    ix = 3
    # Num is a moving target here. As we divide_out_multiples, it decreases.
    # The while statement keeps us iterating until ix equals num. This
    # allows us to drop the ix == num -> break check from divide_out_multiples.
    # If ix == num, the while condition will fail and num will be returned
    while ix < num:
        num = divide_out_multiples(ix, num)
       ix += 2

    return num

if __name__ == "__main__":
    # That big number is the one we're asked to factor
    x = largest_prime_factor(600851475143)
    print x