3
\$\begingroup\$

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:<int> - An number to factor.
    Return:
        type:<arr> - 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 > 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 > 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()
\$\endgroup\$
2
\$\begingroup\$

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 > 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 > 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 > 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 > 0
    d = 2
    while d * d <= n:
        while n % d == 0:
            n //= d
            yield d
        d += 1
    if n > 1:  # to avoid 1 as a factor
        assert d <= n
    yield n
\$\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.