Finding divisors of a number using Python

by Alex
Finding divisors of a number using Python

Here’s a problem I recently tried to solve: given an integer n, what are all its divisors? A divisor, also known as a factor or multiplier, is an integer m by which n is divisible without a remainder. For example, the divisors of 12 are 1, 2, 3, 4, 6, and 12. I ended up writing something with itertools, and my code uses some interesting things from number theory. I don’t know if I’ll come back to it again, but I thought I’d write this article because my attempts to solve the above question turned into a rather amusing exercise.

The simplest approach

If we want to find all the numbers that divide n without a remainder, we can just go through the numbers from 1 to n:

def get_all_divisors_brute(n):

for i in range(1, int(n / 2) + 1):
if n % i == 0:
yield i
yield n

In fact, we only need to get to n/2, because anything greater than that value is guaranteed not to be a divisor of n – if you divide n by something greater than n/2, the result will not be an integer. This code is very simple, and for small values of n it works quite well, but it is quite inefficient and slow in other cases. As n increases, the execution time increases linearly. Can we do better?

Factoring

In my project, I worked mostly with factorials. The factorial of a number n, denoted by n!, is the product of all integers from 1 to n inclusive. For example: 8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 Since factorials consist mostly of small multipliers, I decided to try to get a list of divisors by first identifying the smallest of them. In particular, I looked for prime multipliers, that is, those that are also prime numbers. (A prime number is a number whose only divisors are itself and 1. For example, 2, 3, and 5 are prime, but 4 and 6 are not.) Here is a function that finds the prime divisors of number n:

def get_prime_divisors(n):

i = 2
while i * i <= n:
if n % i == 0:
n /= i
yield i
else:
i += 1

if n > 1:
yield n

This is similar to the previous function that uses the enumeration of divisors: we keep trying multipliers, and if we find a suitable one, we divide by it. Otherwise, we check the next number. This is a pretty standard approach to finding prime multipliers. We can now use this method to get the factorization of a number, that is, to write it as a product of prime numbers. For example, the factorization of number 8! looks like this: 8! = 2^7 × 3^2 × 5 × 7 Calculating this factorization is relatively efficient, especially for factorials, because since all the prime multipliers are very small, you don’t need to do many divisions. There is a statement in number theory called the basic theorem of arithmetic, which states that prime factorizations (decompositions) are unique: for any number n, there is only one way to represent it as a product of prime multipliers. (I won’t give the proof here, but you can find it on Wikipedia.) This gives us a way to find divisors by going through all combinations of prime factors. The prime factors of any m divisor of n must be in the subset of prime factors of n, otherwise m would not divide number n.

Transition from factorization to divisors

First, let’s decompose the original number into prime factors with the “multiplicity”, that is, we should get a list of all the factors and the number of times each of them occurs in the factorization:

import collections

def get_all_divisors(n):
primes = get_prime_divisors(n)

    primes_counted = collections.Counter(primes)

   ...

Then, let’s go ahead and raise each prime number to all the degrees that might appear in a possible divisor n.

def get_all_divisors(n):

...
divisors_exponentiated = [
[div ** i for i in range(count + 1)]
for div, count in primes_counted.items()
]

For example, for 8! the presented code will give us the following:

[
    [1, 2, 4, 8, 16, 32, 64, 128],  // 2^0, 2^1, ..., 2^7
    [1, 3, 9],  // 3^0, 3^1, 3^2
    [1, 5],
    [1, 7],
]

Then, to get the divisors, we can use the rather handy function itertools.product, which takes iterable objects as input and returns all possible ordered combinations of their elements. In our case, it picks one number from each list with exponentiation, and then, multiplying them together, we get the next divisor n.

import itertools

def calc_product(iterable):
acc = 1
for i in iterable:
acc *= i
return acc

def get_all_divisors(n):
...

for prime_exp_combination in itertools.product(*divisors_exponentiated):
yield calc_product(prime_exp_combination)

Thus, we find all the divisors of n (although, unlike the previous functions, they are not sorted).

Put all of them together

Putting it all together, we get the following function for calculating the divisors of n:

import collections
import itertools


def get_prime_divisors(n):
    i = 2
   while i * i <= n:
       if n % i == 0:
            n /= i
yield i
       else:
            i += 1

   if n > 1:
yield n


def calc_product(iterable):
    acc = 1
   for i in iterable:
        acc *= i
   return acc


def get_all_divisors(n):
primes = get_prime_divisors(n)

    primes_counted = collections.Counter(primes)

divisors_exponentiated = [
       [div ** i for i in range(count + 1)]
       for div, count in primes_counted.items()
   ]

for prime_exp_combination in itertools.product(*divisors_exponentiated):
yield calc_product(prime_exp_combination)

print(list(get_all_divisors(40320)) # 8!

This implementation is very efficient, especially when you have a lot of small prime multipliers, as in the case of the factorials I’ve been working with. I don’t know how well it will perform in the general case, and if you do serious scientific calculations, I’m sure you can easily find already implemented and optimized algorithms for this kind of thing.

Related Posts

LEAVE A COMMENT