Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

People also ask

How do you find all the divisors of a given number?

The formula for calculating the total number of divisor of a number ′n′ where n can be represent as powers of prime numbers is shown as. If N=paqbrc . Then total number of divisors =(a+1)(b+1)(c+1).

How do I find all the divisors of a number in Python?

Answer. Python does not include a built-in function to obtain all the divisors of a number, but you can do this fairly easily using a for loop and an if statement. To find all the divisors of a number, we can utilize the modulo % operator, which returns the remainder after division.


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.


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]

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

Divisors of a 28

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


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