Returning a list of divisors for a number

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

-
I've changed the bottom for loop to be for i in range(1, len(divisors) - 2): for j in range(i + 1, len(divisors) - 1): if not orig_num % (i * j): divisors.append(i * j) but it doesn't read well here. – Jack J Feb 22 '13 at 9:38

• 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.

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)])

-
Thanks. I'll review this over the next few days. – Jack J Feb 23 '13 at 13:25

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.

-