Finding all divisors of an integer

The problem is to find all divisors of a given integer n.

(It may be better to implement a true prime generator, rather than a fixed set, as discussed with examples here, but that was not my immediate concern. Also, I am aware that there are much faster algorithms to generate fixed number of prime numbers—I am avoiding them until I fully understand the algorithm.)

```
import functools
import itertools
import operator

def prime_generator(n):
"""
Sieve of Eratosthenes
Create a candidate list within which non-primes will be
marked as None.
"""
cand = [i for i in range(3, n + 1, 2)]
end = int(n ** 0.5) // 2

# Loop over candidates (cand), marking out each multiple.
for i in range(end):
if cand[i]:
cand[cand[i] + i::cand[i]] = [None] * (
(n // cand[i]) - (n // (2 * cand[i])) - 1)

# Filter out non-primes and return the list.
return [2] + [i for i in cand if i]

primes_list = prime_generator(100000)

def factorize(n):
prime_multiples = []
for item in primes_list:
if item > n:
break
else:
while n > 1:
if n % item == 0:
n //= item
prime_multiples.append(item)
else:
break
return prime_multiples

def calculate_divisors(n):
prime_multiples_list = factorize(n)

"""
construct unique combinations
A, B, B, C --> A, B, C, AB, AC, BB, BC, ABC, ABB, BBC
"""
unique_combinations = set()
for i in range(1, len(prime_multiples_list)):
unique_combinations.update(
set(itertools.combinations(prime_multiples_list, i)))

# multiply elements of each unique combination
combination_product = list(functools.reduce(operator.mul, i)
for i in unique_combinations)
combination_product.sort()

return combination_product

print(calculate_divisors(12500))
>>> [2, 4, 5, 10, 20, 25, 50

Lazy generators

Most often in Python you do not want to build an actual list and return it.

If I want to sum the divisors of a number, and there are many, I will waste a lot of space if I put them in a list first.

Also, not creating a list is even shorter, you just give out the elements one by one from the function:

def factorize(n):
    for item in primes_list:
        if item > n:
            break
        else:
            while n > 1:
                if n % item == 0:
                    n //= item
                    yield item
                else:
                    break

Reduce nesting

You got some serious nesting going on, each level of nesting is a level of complexity so getting it a bit down is positive. Luckily if we break we do not need an else: the code after will not be executed anyway:

def factorize(n):
    for item in primes_list:
        if item > n:
            break

        while n > 1:
            if n % item != 0:
                break
            n //= item
            yield item

Still two nested loops, but the situation is becoming more manageable.

Now let me re-factor the while loop away:

def how_many_times_divides(n, div):
    """
    >>> list(how_many_times_divides(40, 2))
    [2, 2, 2]
    """
    while n > 1:
        if n % div != 0:
            break
        n //= div
        yield div

And now factorize is starting to look nice and small:

def factorize(n):
    """
    >>> list(factorize(480))
    [2, 2, 2, 2, 2, 3, 5]
    """
    for item in primes_list:
        if item > n:
            break
        yield from how_many_times_divides(n, item)

Doctests

You may have noted that I added some examples of usage in the doc-strings of this functions. They are actually automatically runnable with doctests and I highly recommend them when writing numerical code.

Avoid unnecessary assignments & mutation

It is just simpler to return the expression:

combination_product = list(functools.reduce(operator.mul, i)
                           for i in unique_combinations)
combination_product.sort()

return combination_product

Becomes:

return sorted(functools.reduce(operator.mul, i)
                 for i in unique_combinations)

Note that I omitted list as it was not really needed.

StackExchange Code Review Q#113018, answer score: 4