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

Solution 1:

Given your factorGenerator function, here is a divisorGen that should work:

def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

The overall efficiency of this algorithm will depend entirely on the efficiency of the factorGenerator.

Solution 2:

To expand on what Shimi has said, you should only be running your loop from 1 to the square root of n. Then to find the pair, do n / i, and this will cover the whole problem space.

As was also noted, this is a NP, or 'difficult' problem. Exhaustive search, the way you are doing it, is about as good as it gets for guaranteed answers. This fact is used by encryption algorithms and the like to help secure them. If someone were to solve this problem, most if not all of our current 'secure' communication would be rendered insecure.

Python code:

import math

def divisorGenerator(n):
    large_divisors = []
    for i in xrange(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n / i)
    for divisor in reversed(large_divisors):
        yield divisor

print list(divisorGenerator(100))

Which should output a list like:

[1, 2, 4, 5, 10, 20, 25, 50, 100]

Solution 3:

I think you can stop at math.sqrt(n) instead of n/2.

I will give you example so that you can understand it easily. Now the sqrt(28) is 5.29 so ceil(5.29) will be 6. So I if I will stop at 6 then I will can get all the divisors. How?

First see the code and then see image:

import math
def divisors(n):
    divs = [1]
    for i in xrange(2,int(math.sqrt(n))+1):
        if n%i == 0:
            divs.extend([i,n/i])
    divs.extend([n])
    return list(set(divs))

Now, See the image below:

Lets say I have already added 1 to my divisors list and I start with i=2 so

So at the end of all the iterations as I have added the quotient and the divisor to my list all the divisors of 28 are populated.

Source: How to determine the divisors of a number

Solution 4:

Although there are already many solutions to this, I really have to post this :)

This one is:

• readable
• short
• self contained, copy & paste ready
• quick (in cases with a lot of prime factors and divisors, > 10 times faster than the accepted solution)
• python3, python2 and pypy compliant

Code:

def divisors(n):
    # get factors and their counts
    factors = {}
    nn = n
    i = 2
    while i*i <= nn:
        while nn % i == 0:
            factors[i] = factors.get(i, 0) + 1
            nn //= i
        i += 1
    if nn > 1:
        factors[nn] = factors.get(nn, 0) + 1

    primes = list(factors.keys())

    # generates factors from primes[k:] subset
    def generate(k):
        if k == len(primes):
            yield 1
        else:
            rest = generate(k+1)
            prime = primes[k]
            for factor in rest:
                prime_to_i = 1
                # prime_to_i iterates prime**i values, i being all possible exponents
                for _ in range(factors[prime] + 1):
                    yield factor * prime_to_i
                    prime_to_i *= prime

    # in python3, `yield from generate(0)` would also work
    for factor in generate(0):
        yield factor

Solution 5:

An illustrative Pythonic one-liner:

from itertools import chain
from math import sqrt

def divisors(n):
    return set(chain.from_iterable((i,n//i) for i in range(1,int(sqrt(n))+1) if n%i == 0))

But better yet, just use sympy:

from sympy import divisors