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
Andrea Ambu
Updated on January 06, 2022Comments
-
Andrea Ambu over 2 years
Here's the very dumb way:
def divisorGenerator(n): for i in xrange(1,n/2+1): if n%i == 0: yield i yield n
The result I'd like to get is similar to this one, but I'd like a smarter algorithm (this one it's too much slow and dumb :-)
I can find prime factors and their multiplicity fast enough. I've an generator that generates factor in this way:
(factor1, multiplicity1)
(factor2, multiplicity2)
(factor3, multiplicity3)
and so on...i.e. the output of
for i in factorGenerator(100): print i
is:
(2, 2) (5, 2)
I don't know how much is this useful for what I want to do (I coded it for other problems), anyway I'd like a smarter way to make
for i in divisorGen(100): print i
output this:
1 2 4 5 10 20 25 50 100
UPDATE: Many thanks to Greg Hewgill and his "smart way" :) Calculating all divisors of 100000000 took 0.01s with his way against the 39s that the dumb way took on my machine, very cool :D
UPDATE 2: Stop saying this is a duplicate of this post. Calculating the number of divisor of a given number doesn't need to calculate all the divisors. It's a different problem, if you think it's not then look for "Divisor function" on wikipedia. Read the questions and the answer before posting, if you do not understand what is the topic just don't add not useful and already given answers.
-
Andrea Ambu over 15 yearswow it took 0.01 for calculating all divisors of 100000000 against the 39s that took the dumb way (stopping at n/2) very cool, thank you!
-
Matthew Scharley over 15 yearsFactors are ALWAYS generated in pairs, by virtue of the definition. By only searching to sqrt(n), you're cutting your work by a power 2.
-
Andrea Ambu over 15 yearsIt's very faster than the version in my post, but it's still too slow than the version using prime factors
-
Matthew Scharley over 15 yearsI agree this isn't the best solution. I was simply pointing out a 'better' way of doing the 'dumb' search that would already save alot of time.
-
Matthew Scharley over 15 yearsFor those of us who don't understand Pythonese, what is this actually doing?
-
Greg Hewgill over 15 yearsmonoxide: this computes all multiplicative combinations of the given factors. Most of it should be self-explanatory; the "yield" line is like a return but keeps going after returning a value. [0]*nfactors creates a list of zeros of length nfactors. reduce(...) computes the product of the factors.
-
Jamie over 15 yearsFactorization has not been shown to be NP-hard. en.wikipedia.org/wiki/Integer_factorization And the problem was to find all the divisors given that the prime factors (the hard part) had already been found.
-
Matthew Scharley over 15 yearsWhich means factorisation is an NP-hard algorithm by extension. The fact they already have the prime factors is beside the point. The example given was exhaustive search, which is slow and hard.
-
jfs over 15 yearsIn Python 2.6 there is a itertools.product().
-
jfs over 15 yearsA version that use generators instead of list.append everywhere could be cleaner.
-
jfs over 15 yearsSieve of Eratosthenes could be used to generate prime numbers less then or equal sqrt(n) stackoverflow.com/questions/188425/project-euler-problem#193605
-
jfs over 15 yearsCoding style: exponents = [k**x for k, v in factors.items() for x in range(v+1)]
-
klenwell over 11 yearsFor listexponents: [[k**x for x in range(v+1)] for k,v in factors.items()]
-
Greg Hewgill over 11 years@SpeckiniusFlecksis: No reason,
operator.mul
would work equally well there. -
GinKin about 10 yearsIs that python ? Anyway, it's not python 3.x for sure.
-
user448810 about 10 yearsIt's pseudocode, which ought to be simple to translate to python.
-
Veedrac almost 10 yearsThe questioner asked for a better algorithm, not just a prettier format.
-
Abhishek almost 10 yearsif i is not n / i: should be if i != n / i: , for values whose square root is greater than 256 'is' will not work.
-
Jens Munk over 9 yearsYou need to use range(1,n+1) to avoid division by zero. Also, you need to use float(n) for the first division if using Python 2.7, here 1/2 = 0
-
Tomasz Gandor over 9 yearsThis is of course dramatically better than dividing by every number up to n/2 or even sqrt(n), but this particular implementation has two drawbacks: quite innefective: tons of multiplication and exponentiation, repeatedly multiplying the same powers etc. Looks Pythonic, but I don't think Python is about killing performance. Problem two: the divisors are not returned in order.
-
Paddy3118 over 9 yearsThanks Greg. Your algorithm inspired my more functional version here: rosettacode.org/wiki/Proper_divisors#Python:_From_prime_factors
-
Kukosk over 9 yearsfor small numbers, it's way faster than the version using prime factors
-
AnnanFay over 7 yearsI seem to be getting an error:
NameError: global name 'prime_factors' is not defined
. None of the other answers, nor the original question, defines what this does. -
Rafa0809 about 7 yearsI would replace
while i*i <= nn
bywhile i <= limit
, wherelimit = math.sqrt(n)
-
Rafa0809 about 7 yearsNice, nice!!
math.sqrt(n) instead of n/2
is mandatory for elegance -
jasonleonhard almost 7 yearsThis is incorrect. You forgot n is divisible by itself.
-
Riyaz Mansoor almost 7 years3 years late, better late than never :) IMO, this is the simplest, shortest code to do this. I don't have a comparison table, but I can factorize and compute divisors for up to a million in 1s on my i5 portable laptop.
-
Kyu96 over 5 yearsWhats the name of the algorithm used to find the primes and to factorize? Because I want to implement this in C# ..
-
Geoffroy CALA over 5 yearsNice answer. Simple and clear. But for python 3 there are 2 necessary changes: n/i should be typed using int(n/i) cause n/i produces float number. Also rangex is deprecated in python 3 and has being replaced by range.
-
Jonath P almost 4 yearstypo: return facts => return faclist
-
Mark Moretto over 3 years@GeoffroyCALA He could also use
n//i
. -
Max about 3 yearsNice idea, but when you posted this, we already had sympy.divisors which should choose the most efficient way to compute it.
-
E. Zeytinci over 2 yearsWhile this code snippet may be the solution, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.
-
Thomas Browne over 2 yearsnitpick: repeated integer square roots eg divisors(16) or divisors(100).