4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Jack J Feb 22 '13 at 9:38
3
\$\begingroup\$
  • 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)])
\$\endgroup\$
2
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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