Best way to find divisors of a number

Question

I have a function that finds the prime divisors of a number and returns a list of its prime factors:

def prime_factors(n, listFact=[]):
    end = floor(sqrt(n))
    if n == 1:
        return listFact
    elif n % 2 == 0:
        return prime_factors(n // 2, listFact + [2])
    elif n % 3 == 0:
        return prime_factors(n // 3, listFact + [3])
    for j in range(6, end + 2, 6):
        p1, p2 = j - 1, j + 1
        if n % p1 == 0:
            return prime_factors(n // p1, listFact + [p1])
        elif n % p2 == 0:
            return prime_factors(n // p2, listFact + [p2])
   return listFact + [n]

So, prime_factors(120) = [2, 2, 2, 3, 5].

How can I calculate the divisors optimally from this list? My approach was very cumbersome, by adding a function called counts that returns a dictionary of the times each factor appears. So, counts(prime_factors(120)) = {2: 3, 3: 1, 5: 1}. The program is:

def find_divisors_v2(n):
    dict_primes = counts(prime_factors(n))
    big_list = []
    for k, v in dict_primes.items():
        big_list.append([(k, i) for i in range(v+1)])
    divisors_perms = list(itertools.product(*big_list))
    divisors = []
    for perm in divisors_perms:
        d = 1
        for i in perm:
            d *= i[0]**i[1]
        divisors.append(d)
    return divisors

But surprisingly it is faster than calculating it on the usual manner, i.e.:

def find_divisors(n):
    divisors = []
    bound = ceil(sqrt(n)) + 1
    for d in range(1, bound):
        if n // d == d:
            divisors.append(d)
        elif n % d == 0:
            divisors.append(d)
            divisors.append(n//d)
    return divisors

Is there a way to extract the divisors from a list of the prime factors that is more computationally efficient? Or maybe do it by modifying the prime_factors function?

Answer 1

The one time I had to do this, I essentially wrote the same as find_divisors2, but optimized so that I wasn't calculating the same powers over and over again.

def factor_list(value: int) -> Sequence[int]:
    # prime_factor_list is something like ((2, 3),(3, 1)) for 24
    def recurse(prime_factor_list) -> Sequence[int]:
        if not prime_factor_list:
            return [1]
        *start_factor_list, (prime, count) = prime_factor_list
        sub_factors = recurse(start_factor_list)
        powers = [prime ** i for i in range(0, count + 1)]
        return [factor * power for factor in sub_factors for power in powers]

    # prime_factors returns a list of tuple[int, int] giving prime and power
    result = sorted(recurse(prime_factors(value)))