Computing a list of divisors of a number

Question

I developed the following Python functions when solving a few Project Euler problems, and since I'm not that familiar with Python, I'm curious at how I could improve them.

The code consists of a data holder class, and a few functions.

Option class:

This object stores data for a combination option. It has two data members:

• value: the value of the option
• count: how many times this option can be chosen

class Option:
 def __init__(self, value, count):
 self.value = value
 self.count = count

Get Prime Factorization:

This function calculates a number's prime factorization. It returns the factorization as a list of Options where the option's value is the prime and it's count is the power.

def getPrimeFactorization(n):
 f = []
 nth = 0
 while n > 1:
 prime = nthPrime(nth)
 if n % prime == 0:
 f.append(Option(prime, 1))
 n = n // prime
 while n % prime == 0:
 f[-1].count += 1
 n = n // prime
 nth += 1
 return f

Get Combinations:

To calculate the combinations, I use getCombinationsIncrement to iterate through each possible combination. The index is the index of the current option, options is the list of Options, and chosen is the number of times the Option will be chosen.

def getCombinationsIncrement(index, options, chosen):
 if index >= len(options):
 return False
 else:
 chosen[index] += 1
 if chosen[index] > options[index].count:
 chosen[index] = 0
 return getCombinationsIncrement(index + 1, options, chosen)
 else:
 return True

The options parameter is a list of options, combine is the function used to combine options, base is the base amount to combine with other values (it's similar to reduce if your familiar with JavaScript).

def getCombinations(options, combine, base):
 combos = [base]
 chosen = [0] * len(options)
 while getCombinationsIncrement(0, options, chosen):
 combos.append(base)
 for i in range(len(options)):
 for _ in range(chosen[i]):
 combos[-1] = combine(combos[-1], options[i].value)
 combos.sort()
 return combos

Get Divisors

Using the functions above it's easy to calculate all the divisors of a number.

def multiply(x, y):
 return x * y
def getDivisors(n):
 return getCombinations(getPrimeFactorization(n), multiply, 1)

---

My primary concern is with the getCombinationsIncrement function. I'd like it to be scoped only into the getCombinations function, and I don't particularly like having to make a class to fix that. It also might not be the best way to go about creating the combinations.

Answer 1

You code is hard to understand. Very hard.

In Python we prefer iteration over recursion, not only does recursion limit you to a maximum depth of 1000 function calls, it also has severe performance impacts.

You should:

• Use snake_case in Python not camelCase. The only time you use CamelCase is when creating a class.
• Start using generators. In most cases you can just replace list.append with a yield.
• Change nthPrime to be a generator, say primes. As I'm not here to re-write nthPrime you can just use itertools.count to get an infinite generator.
• Don't duplicate logic before and during a loop. In prime_factorization, you wrote the floor division, n //= prime, twice.
• It's simpler to use a for loop and break from it, than while looping with a condition and manually taking the next item.
• You can use collections.namedtuple to remove the need to create your own class.

Merging the above together for just prime_factorization can get you:

from collections import namedtuple
from itertools import count
Option = namedtuple('Option', 'value count')
def primes():
 for i in count():
 yield nthPrime(i)
def prime_factorization(n):
 for prime in primes():
 count = 0
 while n % prime == 0:
 count += 1
 n //= prime
 if count:
 yield Option(prime, count)
 if n <= 1:
 break

After this you want to move more code into combinations, so that it's self contained in getCombinationsIncrement, and to rename it combinations.

• Change combinations to instead yield a tuple of chosen.
• Create chosen within combinations.
• Pass a single one dimensional list to combinations so that it's more usable later.
• When you finish running through all of options without yielding, you want to stop. To do this you can use the for ... else syntax and just break.

This should be able to get you:

def combinations(options):
 chosen = [0] * len(options)
 while True:
 for i, option in enumerate(options):
 chosen[i] += 1
 if chosen[i] > option:
 chosen[i] = 0
 break
 yield tuple(chosen)
 else:
 break

Finally we want to change combinations_reduce to use combinations.

• First you should change options from a 2d lists to two 1d lists. You should want to get values and counts into their own lists. And so you can use zip with the argument unpacking operator, *, to expand the list to \$n\$ 2 long lists.

• You want to create combos off the bat, and can use enumerate to get the current index.

  Alternately you could try using yield instead, and off-load the sorting to the user.

• You can use reduce to replace your innermost loop.
• You can change the input to use default variables of operators.mul and 1. This simplifies the usage, as you don't need to specify as much.

This can get you:

def combinations_reduced(options, combine=mul, base=1):
 values, counts = zip(*options)
 combos = [base] * len(counts)
 for i, chosen in enumerate(combinations(counts), 1):
 for j, value in enumerate(values):
 combos[i] = reduce(combine, [combos[i]] + [value] * chosen[j])
 combos.sort()
 return combos
def get_divisors(n):
 return combinations_reduced(prime_factorization(n))

• Joshua Dawson: Thanks for the tips! I'm still getting used to Python, and I wrote the combinations code awhile ago. Looking forward to implement your recommendations.
• Peilonrayz: @JoshDawson No problem. Just prioritize loops over recursion in Python and you'll be set, :)