# 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:<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()


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