Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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
share|improve this question
    
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
add comment

2 Answers

up vote 1 down vote accepted
  • 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)])
share|improve this answer
    
Thanks. I'll review this over the next few days. –  Jack J Feb 23 '13 at 13:25
add comment

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.