Third project Euler solution The things I'm interested the most from the review are:


The performance of the code
Overall review of the code structure, styling rules and naming conventions.



  What is the largest prime factor of the number 600851475143 ?


import math
#----------------------------------------------------------------------------------
def prime_factorization(num_to_factor):
    """Calculates the prime factors of the input number based on 
    Pollard's rho algorithm for integer factorization.

    Arguments:
        type:&lt;int&gt; - An number to factor.
    Return:
        type:&lt;arr&gt; - An array holding the prime factors of input number.
    """

    #------------------------------------------------------------------------------
    def calc_factor(num_to_factor):

        x,x_fixed = 2,2
        cycles = 2
        factor = 1

        while factor == 1:
            for counter in range(cycles):
                if factor &gt; 1: break    

                x = (x * x - 1) % num_to_factor
                factor = math.gcd(x - x_fixed, num_to_factor)

            x_fixed = x
            cycles *= 2
        return factor

    factors = []
    while num_to_factor &gt; 1:

        # Gets the smallest factor of (num_to_factor) and appends it to the array.
        # Divides the (num_to_factor) with it, and starts searching for the next factor.
        factor = calc_factor(num_to_factor)
        factors.append(factor)
        num_to_factor //= factor

    return factors

#----------------------------------------------------------------------------------
def main():
    n = 600851475143
    print(' Prime factorization of {} is: {}'.format(n, prime_factorization(n)))
#----------------------------------------------------------------------------------
if __name__ == "__main__":
    main()
Disclaimer: I have never used or implemented Pollard's rho algorithm.

calc_factor

I think this function does not need to be a nested function. It could be a normal function on its own (and thus be documented accordingly).

Maybe, its name and the name for its parameter could be updated for something that sounds more usual, maybe get_factor(n)...

Instead of checking if factor &gt; 1 at the beginning of the loop, you could check if just after updating the value of factor.

Also, instead of trying to break out of 2 loops, you could simply return the value directly if factor &gt; 1 and you realise you don't need to check the value of factor in other places.

You'd get something like:

def get_factor(n):
    x,x_fixed = 2,2
    cycles = 2

    while True:
        for counter in range(cycles):
            x = (x * x - 1) % n
            factor = math.gcd(x - x_fixed, n)
            if factor &gt; 1:
                return factor
        x_fixed = x
        cycles *= 2


prime_factorization

Here again, you could probably rename the parameter for something shorter.

I am not sure what the conventional way to do is but once you get a factor with the other functions, it may be worth checking how many times it divides.

Potential issues

Finally, I have the feeling that the algorithm does not provide an real prime factorisation because the factors returned by calc_factor are not always prime factors, they are just "random" factors.

If it may help you, here is the function I've used many times for Project Euler factorisations:

def prime_factors(n):
    """Yields prime factors of a positive number."""
    assert n &gt; 0
    d = 2
    while d * d &lt;= n:
        while n % d == 0:
            n //= d
            yield d
        d += 1
    if n &gt; 1:  # to avoid 1 as a factor
        assert d &lt;= n
    yield n