My code is very slow when it comes to very large numbers.
def divisors(num):
divs = 1
if num == 1:
return 1
for i in range(1, int(num/2)):
if num % i == 0:
divs += 1
elif int(num/2) == i:
break
else:
pass
return divs
For 10^9 i get a run time of 381.63s.
Here is an approach that determines the multiplicities of the various distinct prime factors of n. Each such power, k, contributes a factor of k+1 to the total number of divisors.
import math
def smallest_divisor(p,n):
#returns the smallest divisor of n which is greater than p
for d in range(p+1,1+math.ceil(math.sqrt(n))):
if n % d == 0:
return d
return n
def divisors(n):
divs = 1
p = 1
while p < n:
p = smallest_divisor(p,n)
k = 0
while n % p == 0:
k += 1
n //= p
divs *= (k+1)
return divs - 1
It returns the number of proper divisors (so not counting the number itself). If you want to count the number itself, don't subtract 1 from the result.
It works rapidly with numbers of the size 10**9, though will slow down dramatically with even larger numbers.
Consider this:
import math
def num_of_divisors(n):
ct = 1
rest = n
for i in range(2, int(math.ceil(math.sqrt(n)))+1):
while rest%i==0:
ct += 1
rest /= i
print i # the factors
if rest == 1:
break
if rest != 1:
print rest # the last factor
ct += 1
return ct
def main():
number = 2**31 * 3**13
print '{} divisors in {}'.format(num_of_divisors(number), number)
if __name__ == '__main__':
main()
We can stop searching for factors at the square root of n. Multiple factors are found in the while loop. And when a factor is found we divide it out from the number.
edit:
@Mark Ransom is right, the factor count was 1 too small for numbers where one factor was greater than the square root of the number, for instance 3*47*149*6991. The last check for rest != 1 accounts for that.
The number of factors is indeed correct then - you don't have to check beyond sqrt(n) for this.
Both statements where a number is printed can be used to append this number to the number of factors, if desired.
Division is expensive, multiplication is cheap.
Factorize the number into primes. (Download the list of primes, keep dividing from the <= sqrt(num).)
Then count all the permutations.
If your number is a power of exactly one prime, p^n, you obvioulsy have n divisors for it, excluding 1; 8 = 2^3 has 3 divisors: 8, 4, 2.
In general case, your number factors into k primes: p0^n0 * p1^n1 * ... * pk^nk. It has (n0 + 1) * (n1 + 1) * .. * (nk + 1) divisors. The "+1" term counts for the case when all other powers are 0, that is, contribute a 1 to the multiplication.
Alternatively, you could just google and RTFM.
Here is an improved version of my code in the question. The running time is better, 0.008s for 10^9 now.
def divisors(num):
ceiling = int(sqrt(num))
divs = []
if num == 1:
return [1]
for i in range(1, ceiling + 1):
if num % i == 0:
divs.append(num / i)
if i != num // i:
divs.append(i)
return divs
It is important for me to also keep the divisors, so if this can still be improved I'd be glad.
