Делители
Есть такая задача: сколько у числа 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(sum(sieve[lo:hi]) / (hi - lo))
hi = lo
fig, ax = plt.subplots(figsize=(5, 2.7), 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}.
