I have put together the following code in order to determine if a number has an odd or even number of divisors. The code works well with relatively small numbers but once a larger number like 9 digits is entered it hangs up.
def divisors(n):
num = len(set([x for x in range(1,n+1) if not divmod(n,x)[1]]))
if (num != 0 and num % 2 == 0):
return 'even'
else:
return 'odd'
what can I do to make this more efficient?
Here's your problem:
num = len(set([x for x in range(1,n+1) if not divmod(n,x)[1]]))
This constructs a list, then constructs a set out of that list, then takes the length of the set. You don't need to do any of that work (range(), or xrange() for that matter, does not produce repeated objects, so we don't need the set, and sum() works on any iterable object, so you don't need the list either). While we're on the subject, divmod(n, x)[1] is just a very elaborate way of writing n % x, and consumes a little bit of extra memory to construct a tuple (which is immediately reclaimed because you throw the tuple away). Here's the fixed version:
num = sum(1 for x in xrange(1,n+1) if not n % x)
You do not need to test every possible divisor, testing up to sqrt(n) is enough. This will make your function O(sqrt(n)) instead of O(n).
import math
def num_divisors(n):
sqrt = math.sqrt(n)
upper = int(sqrt)
num = sum(1 for x in range(1, upper + 1) if not n % x)
num *= 2
if upper == sqrt and num != 0:
num -= 1
return num
In my benchmarks using python2 this is 1000 times faster than sum(1 for x in range(1, n + 1) if not n % x) with n = int(1e6) and 10000 times faster for 1e8. For 1e9 the latter code gave me a memory error, suggesting that the whole sequence is stored in memory before doing the sum because in python 2 range() returns a list and I should be using xrange() instead. For python3 range() is fine.
