Returning a list of divisors for a number

Question

This function takes in a number and returns all divisors for that number. list_to_number() is a function used to retrieve a list of prime numbers up to a limit, but I am not concerned over the code of that function right now, only this divisor code. I am planning on reusing it when solving various Project Euler problems.

def list_divisors(num):
    ''' Creates a list of all divisors of num
    '''
    orig_num = num
    prime_list = list_to_number(int(num / 2) + 1)
    divisors = [1, num]
    for i in prime_list:
        num = orig_num
        while not num % i:
            divisors.append(i)
            num = int(num / i)
    for i in range(len(divisors) - 2):
            for j in range(i + 1, len(divisors) - 1):
                if i and j and j != num and not orig_num % (i * j):
                    divisors.append(i * j)
    divisors = list(set(divisors))
    divisors.sort()
    return divisors

Answer 1

• Don't reset num to orig_num (to fasten division/modulo)
• Think functionnaly :
  • From your prime factors, if you generate a new collection with all possible combinations, no need to check your products.
  • It makes harder to introduce bugs. Your code is indeed broken and won't output 20 or 25 (...) as divisors of 100.
  • You can re-use existing (iter)tools.
• Avoid unnecessary convertions (sorted can take any iterable)
• Compute primes as you need them (eg, for 10**6, only 2 and 5 will suffice). Ie, use a generator.

This leads to :

from prime_sieve import gen_primes
from itertools import combinations,  chain
import operator

def prod(l):
   return reduce(operator.mul, l, 1)

def powerset(lst):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    return chain.from_iterable(combinations(lst, r) for r in range(len(lst)+1))

def list_divisors(num):
    ''' Creates a list of all divisors of num
    '''
    primes = gen_primes()
    prime_divisors = []
    while num>1:
       p = primes.next()
       while not num % p:
          prime_divisors.append(p)
          num = int(num / p)

    return sorted(set(prod(fs) for fs in powerset(prime_divisors)))

Now, the "factor & multiplicity" approach like in suggested link is really more efficient. Here is my take on it :

from prime_sieve import gen_primes
from itertools import product
from collections import Counter
import operator

def prime_factors(num):
   """Get prime divisors with multiplicity"""

   pf = Counter()
   primes = gen_primes()
   while num>1:
      p = primes.next()
      m = 0
      while m == 0 :
         d,m = divmod(num,p)
         if m == 0 :
            pf[p] += 1
            num = d
   return pf

def prod(l):
   return reduce(operator.mul, l, 1)

def powered(factors, powers):
   return prod(f**p for (f,p) in zip(factors, powers))


def divisors(num) :

   pf = prime_factors(num)
   primes = pf.keys()
   #For each prime, possible exponents
   exponents = [range(i+1) for i in pf.values()]
   return sorted([powered(primes,es) for es in product(*exponents)])

Answer 2

num/2 should be sqrt(num). And this should also be recalculated in your loop, or at least check to leave the for earlier.

A better prime candidates algorithms might also improve overall performance.

See also What is the best way to get all the divisors of a number?