Делители

Есть такая задача: сколько у числа 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}.