Есть такая задача: сколько у числа n делителей? Вот к примеру у числа 4 три делителя: 1, 2 и 4, а у числа 6 – четыре: 1, 2, 3 и 6. Задачи такого рода часто встречаются на всяческих литкодах, и публика с воодушевлением их колупает. Ну и правильно.

Наивное решение выглядит так:

divisers = [i for i in range(1, n + 1) if n % i == 0]

Его сложность , с этим можно смириться. Решение потоньше имеет сложность , оно построено на том соображении, что, имея делитель числа меньший или равный , ты легко получаешь сопряженный с ним делитель больший (или равный) :

from math import sqrt

divisers = {1, n}
for i in range(2, int(sqrt(n)) + 1):
    if n % i == 0:
        dividers.update([i, n // i])
divisers = sorted(divisers)

Последняя строка вызвана к жизни тем, что проверяющая система (на литкоде, например) хочет получить упорядоченный набор делителей. Изначальный выбор множества как коллекции делителей позволяет обойти ситуацию, когда - точный квадрат, и не войдёт в делители дважды.

Есть ли идея получше? Да, конечно! Смотрите:

def factor(n):
    d, p = {}, 2
    while p * p <= n:
        while not n % p:
            d[p] = d.get(p, 0) + 1
            n //= p
        p += 1
    if 1 < n:
        d[n] = 1
    return d

divisers = [1]
for p, q in factor(n).items():
    shift = -len(divisers)
    divisers += (divisers[shift] * p for _ in range(-shift * q))
divisers.sort()

В этом фрагменте сперва объявляется вспомогательная функция factor, которая возвращает все простые делители n и их степени, которые (в смысле делители в степени) - тоже делители n. Ну например, factor(24) вернёт {2: 3, 3: 1}, что означает 24 == 2 * 2 * 2 * 3.

Затем эти простые делители я всячески между собой перемножаю, и тогда уже получаю все делители числа , и простые и составные. Опытного питониста может смутить предпоследняя строка, "а что, так можно было?" Ну, я иногда такое себе позволяю, а вы уж сами решайте, можно ли такое вам)

А верно ли эта идея получше? К чему вся эта возня с простыми, лишний код? Ведь напорись я на большое простое , или хоть на , где - простое, factor(n) проделает всё те же итераций, только с большими затратами? Мне кажется, да. Смотрите, каждое второе натуральное число - четное, каждое третье - делится на 3 и т.д. Множество чисел содержат небольшие простые множители, и по их нахождении объём оставшихся вычислений снижается кратно. Простые же числа, при продвижении по натуральному ряду в сторону увеличения, встречаются всё реже.

А вот это перемножение простых сомножителей, оно ведь тоже чего-то да стоит? Тут у меня есть неплохой ответ: я подсчитал, сколько делителей в среднем у чисел в пределах первого миллиарда, вот график:

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

import numpy as np
import matplotlib.pyplot as plt

N = 1_333_333_333 # я пойду по отрезкам типа 667..1333, среднее 1000, красивое)
sieve = np.ones(N, dtype=np.uint16) # это типа решета Эратосфена, только другое
buf = np.full(N, 2, dtype=np.uint16) # тут буду укапливать кратность делителей,
                                     # произведенную простым делителем 
i = m = 2 # разберёмся с четными
while i < N:
    sieve[i::i] = m
    i *= 2
    m += 1

for p in range(3, N, 2): # и с нечетными
    if sieve[p] == 1:
        pp = p * p
        while pp < N:
            buf[pp::pp] += 1
            pp *= p
        sieve[p::p] *= buf[p::p]
        buf[p::p] = 2

x, y, hi = [], [], N
while 60 < hi: # чтоб не докапываться до мышей, тьфу, слишком мелких отрезков
    lo = (hi + 1) // 2
    x.append((lo + hi) // 2)
    y.append(np.sum(sieve[lo:hi]) / (hi - lo))
    hi = lo

fig, ax = plt.subplots(figsize=(5, 4), layout='constrained')
plt.xscale('log', base=10)
ax.plot(x, y, label='количество делителей числа\n от его порядка, усредненно')
plt.show()

Бонусом - у числа 1_102_701_600 больше всего на рассмотренном отрезке делителей, 1440. Вот его фактор: {2: 5, 3: 4, 5: 2, 7: 1, 11: 1, 13: 1, 17: 1}.