Оптимизация кода в рамках задачи «Делители»

Замечание по вашему коду:

def dividers(n):
    p = full_factorization(n) # 'p' нигде не используется
    divs = []
    for i in range(1, n + 1):
        if n%i == 0:
            divs.append(i)
    return divs

Моё решение:

Для нахождения множителей числа можно применить более быстрый алгоритм, видео с объяснением на английском - Finding factors of a number.

from math import gcd

def solve(num):
    factors = []
    a = 1
    b = num
    while a < b:
        b = num // a
        if b * a == num:
            factors.append(a)
            # Обработка случая равных множителей, например 'a' = 10 и 'b' 10,
            # при num = 100.
            if a != b:
                factors.append(b)
        a += 1

    factors.sort()
    # Для наглядности
    print("factors", factors, '\n')

    cnt = 0
    # Проверяем все комбинации множителей.
    for i, a in enumerate(factors, 1):
        # Так как список factors отсортирован и состоит из уникальных значений,
        # любое число, находящееся правее текущего, будет больше, 
        # что даёт нам выполнение условия 'a < b'.
        for b in factors[i:]:
            # Если встретилось 'b', которое при умножении на 'a'
            # даёт произведение больше, чем 'num', то текущий цикл
            # можно завершать, так как дальше 'b' будет только увеличиваться.
            if a * b > num:
                break

            if gcd(a, b) == 1:
                # Для наглядности
                print("pair\t", a, b)
                cnt += 1

    return cnt

inpt = 100
print("\nanswer", solve(inpt))

Output

factors [1, 2, 4, 5, 10, 20, 25, 50, 100] 

pair     1 2
pair     1 4
pair     1 5
pair     1 10
pair     1 20
pair     1 25
pair     1 50
pair     1 100
pair     2 5
pair     2 25
pair     4 5
pair     4 25

answer 12

Вы не укладываетесь по времени из-за медленной функции dividers. Она перебирает n чисел чтобы выделить из них делители n. Её можно ускорить, если правильно воспользоваться разложением из full_factorization. Всё остальное работает достаточно быстро потому что делителей мало: любое число n ≤ 10⁸ имеет не более 768 делителей. Но я хочу предложить другой путь, который совмещает производительность O(√n) с относительной простотой кода - не нужно строить все делители чтобы найти ответ.

Обозначим искомое число пар множителей за f(n). Из набора условий ограничивающих пары для f уберём требование a < b и обозначим новое количество пар множителей через g(n). Заметим что каждая пара (a, b) для f соответствует двум парам для g, а именно парам (a, b) и (b, a). Также в g входит одна особенная пара - (1, 1), которой нет соответствия среди пар f. Это неформальное рассуждение приводит к формуле 2f(n) + 1 = g(n).

Дальше будем заниматься вычислением g(n).

Пусть n₁ и n₂ взаимно простые. Покажем что g(n₁)g(n₂) = g(n₁n₂).

Пусть (a₁, b₁) - пара множителей для числа n₁, а (a₂, b₂) - пара множителей для числа n₂. Рассмотрим пару (a₁a₂, b₁b₂). Множители в ней взаимно просты, следовательно эта пара входит в g(n₁n₂).

Обратно. Возьмём любую пару (a, b) из g(n₁n₂). a разлагается в произведение a = a₁a₂, где n₁ : a₁, n₂ : a₂. Разложение существует и единственно, так как n₁ и n₂ взаимно простые. Разложим аналогично b: b = b₁b₂, где n₁ : b₁, n₂ : b₂. Пара (a₁, b₁) соответствует g(n₁), пара (a₂, b₂) соответствует g(n₂).

Так как отображение ((a₁, b₁), (a₂, b₂)) ↔ (a, b) взаимнооднозначное, мощности множеств слева и справа равны. Слева произведение g(n₁)g(n₂), справа g(n). Равенство доказано.

Это свойство g называется мультипликативностью. Мультипликативные функции можно вычислять по разложению числа на простые. Заметим что если p - простое, то g(p^a) = 2a + 1. Проверяется перечислением всех возможных пар. Тогда общая формула для разложения на простые будет:

g(∏p_i^a_i) = ∏(2a_i + 1), где p_i - различные простые.

С теорией покончили. Практика: по разложению n на простые вычислить g(n), затем восстановить f(n) = (g(n) - 1)/2.

Функция g основана на общем алгоритме факторизации числа: сперва из числа удаляется степень двойки, затем проверяется делимость на нечётные числа. Если делится, соответствующий делитель оказывается простым и мы его тоже удаляем из числа. Цикл делает не более (√n)/2 итераций.

import math


def g(n):

    def factor(n, g, p):
        f = 1
        while n % p == 0:
            n //= p
            f += 2
        return n, g * f

    n, g = factor(n, 1, 2)
    i = 3
    n_sqrt = math.isqrt(n)
    while i <= n_sqrt:
        if n % i == 0:
            n, g = factor(n, g, i)
            n_sqrt = math.isqrt(n)
        i += 2
    if n > 1:
        n, g = factor(n, g, n)
    return g


def f(n):
    return (g(n) - 1) // 2


print(f(int(input())))

Работает для n ≤ 10⁸ мгновенно. Цикл в функции g выполняется не более 5000 раз.

$ echo 9699690 | python f.py
3280

$ echo 67108864 | python f.py
26

$ echo 99999989 | python f.py
1

$ echo 91891800 | python f.py
9922