Делитель - представляет собой такое целое число m, при котором n делится без остатка. Например, делителями числа 12 являются 1, 2, 3, 4, 6 и 12.

Самый простейший подход:

Если мы хотим найти все числа, которые делят n без остатка, мы можем просто перебрать числа от 1 до n:

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

На самом деле нам нужно получить только n/2, потому что все, что больше этого значения, гарантированно не будет делителем n — если вы разделите n на что-то большее, чем n/2, результат не будет целым числом.

Этот код очень прост и достаточно хорошо работает при малых значениях n, но в других случаях он довольно неэффективен и медленный. 

С увеличением n время выполнения увеличивается линейно. Можем ли мы сделать лучше?

Факторизация

Факториал числа n, обозначаемый n! — это произведение всех целых чисел от 1 до n включительно. Например:

8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1

Вот функция, которая находит простые делители числа 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

Это похоже на предыдущую функцию с перебором делителей: мы продолжаем пробовать множители, и если находим подходящий, делим на него. В противном случае проверяем следующее число. Это довольно стандартный подход к нахождению простых множителей.

Теперь мы можем использовать этот метод, чтобы получить факторизацию числа, то есть записать его как произведение простых чисел. Например, факторизация числа 8! следующим образом:

8! = 2^7 × 3^2 × 5 × 7

Вычисление такой факторизации относительно эффективно, особенно для факториалов, поскольку вам не нужно много делить, поскольку все простые множители очень малы.

В теории чисел есть утверждение, называемое Фундаментальной теоремой арифметики, в котором говорится, что простые факторизации (разложения) уникальны: для любого числа n существует только один способ представить его как произведение простых множителей.

Это дает нам способ находить делители, перебирая все комбинации простых множителей. Простые множители любого m делителя n должны быть в подмножестве простых множителей n, иначе m не будет делить n.

Переход от факторинга к делителям

Для начала разложим исходное число на простые множители с указанием «кратности», то есть мы должны получить список всех множителей и количество раз, когда каждый из них встречается в факторизации:

import collections

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

    primes_counted = collections.Counter(primes)

    ...

Итак, мы идем дальше и возводим каждое простое число во все степени, которые могут встречаться в возможном делителе n.

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

Например, для 8! представленный код выдаст нам следующее:

[
    [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],
]

Затем для получения делителей мы можем использовать довольно удобную функцию itertools.product, которая берет итерируемые объекты и возвращает все возможные упорядоченные комбинации их элементов. В нашем случае он выбирает число из каждого списка показателей, а затем, когда мы их перемножаем, мы получаем ближайший делитель 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)

Таким образом, мы находим все делители n (хотя, в отличие от предыдущих функций, они не отсортированы).

Складывая все это вместе, мы получаем следующую функцию для вычисления делителей 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!

Такая реализация очень эффективна, особенно когда у вас много маленьких простых множителей.

Источник: pythonru.com