Делитель числа
Целое число \(a\) называется множителем, или делителем целого числа \(b\), если \(a\) делит \(b\). Если \(a\) – множитель \(b\), то мы пишем \(a | b\). Например, множителями числа \(24\) являются \(1, 2, 3, 4, 6, 8, 12, 24\).
Алгоритм поиска делителей числа \(x\)
Число \(x\) можно представить в виде произведения \(a \cdot b\), где \(a \leq \sqrt{x}\) или \(b \leq \sqrt{x}\). Поэтому мы рассматриваем промежуток\([1;\sqrt{x}]\). Следовательно, найти все делители числа можно за время \(O(\sqrt{x})\).
Показанная ниже функция find_dividers находит все делители числа \(x\). Она пытается поделить \(x\) на все целые числа от \(1\) до \(\lfloor \sqrt{x} \rfloor\); если поделить удалось, то числа \(i\) и \(\frac{x}{i}\) являются делителями числа \(x\).
def find_dividers(x):
dividers = []
for i in range(1, isqrt(x) + 1):
if x % i != 0:
continue
dividers.append(i)
if i * i != x:
dividers.append(x // i)
return dividers
Простые числа
Целое число \(n > 1\) называется простым, если его единственными положительными множителями являются \(1\) и \(n.\) Например, числа \(7\), \(19\) и \(41\) простые, а \(35\) – не простое (составное), потому что \(5 \cdot 7 = 35\).
Алгоритм проверки числа \(x\) на простоту
Если целое число \(x\) не простое, то его можно представить в виде произведения \(a \cdot b\), где \(a \leq \sqrt{x}\) или \(b \leq \sqrt{x}\), поэтому среди его множителей обязательно имеется число от \(2\) до \(\lfloor x \rfloor\). Следовательно, проверить простоту числа и найти его разложение на простые множители можно за время \(O(\sqrt{x}).\)
Показанная ниже функция is_prime проверяет, является ли целое число \(x\) простым. Она пытается поделить \(x\) на все целые числа от \(2\) до \(\lfloor x \rfloor\); если ни одно из них не является делителем, то \(x\) простое.
def is_prime(x):
if x < 2:
return False
for i in range(2, isqrt(x) + 1):
if x % i == 0:
return False
return True
Факторизация числа
Факторизацией натурального числа называется его разложение в произведение простых множителей.
Для каждого целого числа \(n > 1\) существует единственная факторизация. Например,
\(12 = 2 \cdot 2 \cdot 3\)
Часто это записывается со степенями простых множителей:
\(12 = 2^2 \cdot 3\)
Таким образом, любое число \(x\) можно представить в виде произведения простых множителей следующим образом:
\(x = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_n^{\alpha_n} = \displaystyle\prod_{i=1}^{n} p_i^{\alpha_i}\)
Алгоритм факторизации числа \(x\)
Функция factorize строит список, содержащий разложение \(x\) на простые множители. Функция делит число \(x\) на его простые множители и добавляет их в список. Процесс заканчивается, когда у \(x\) не останется множителей между \(2\) и \(\lfloor x \rfloor\). Если при этом \(x > 1\), то оно простое и добавляется в качестве последнего множителя.
def factorize(x):
factors = []
for i in range(2, isqrt(x) + 1):
while x % i == 0:
factors.append(i)
x //= i
if x > 1:
factors.append(x)
return factors
Отметим, что каждый простой множитель встречается в этом списке столько раз, какова его степень в разложении x. Например, \(12 = 2^2 \cdot 3\), поэтому функция вернет результат \([2, 2, 3]\).
Обозначим \(\tau(x)\) количество делителей целого числа \(x\). Например, \(\tau(12) = 6\), поскольку делителями \(12\) являются \(1, 2, 3, 6, 12\). Вычислить \(\tau(n)\) можно по формуле:
\(\tau(x) = \displaystyle\prod_{i=1}^{n}({\alpha_i} + 1)\)
потому что для каждого простого \(p_i\) существует \(\alpha_i + 1\) способов выбрать, сколько раз оно входит в множитель. Например, \(12 = 2^2 \cdot 3\), поэтому \(\tau(12) = 3 \cdot 2 = 6\)
Разложение факториала на простые множители
Каждое простое число \(p\) входит в разложение \(n!\) на простые множители в степени определяемой следующей формулой:
\(\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor + \ldots\)
Таким образом,
\(n! = \displaystyle\prod_p p^{ \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor + \ldots},\)
где произведение берётся по всем простым числам. Можно заметить, что для всякого простого \(p\) большего \(n\) соответствующий множитель в произведении равен \(1\); следовательно, произведение можно брать лишь по простым \(p\), не превосходящим \(n\).
Алгоритм подсчёта количества делителей числа \(x\)
Функция dividers_count использует функцию factorize для факторизации числа \(x\), а затем по формуле выше находит количество делителей числа \(x\).
def dividers_count(x):
factors = factorize(x)
n = len(factors)
factors.append(-1)
count = 1
curr = 1
for i in range(n):
if factors[i] == factors[i+1]:
curr += 1
else:
count *= curr + 1
curr = 1
return count
Обозначим \(\sigma(x)\) сумму всех делителей числа \(x\). Например, \(\sigma(12) = 28\), т. к. \(1 + 2 + 3 + 4 + 6 + 12 = 28\). Значение \(\sigma(x)\) вычисляется по формуле:
\(\sigma(x) = 1 + p_i + \ldots + p_i^{\alpha_i} = \displaystyle\prod_{i=1}^{n} \frac{p_i^{\alpha_i + 1} - 1}{p_i - 1}\)
следующей из формулы суммы геометрической прогрессии. Например,
\(\sigma(12) = \frac{2^3-1}{2-1} \cdot \frac{3^2-1}{3-1} = 28\)
Алгоритм нахождения суммы всех делителей числа \(x\)
Функция dividers_sum использует функцию factorize для факторизации числа \(x\), а затем по формуле выше находит сумму всех делителей числа \(x\).
def dividers_sum(x):
factors = factorize(x)
n = len(factors)
factors.append(-1)
summa = 1
curr = 1
for i in range(n):
if factors[i] == factors[i+1]:
curr += 1
else:
ch = factors[i] ** (curr + 1) - 1
zn = factors[i] - 1
summa *= ch // zn
curr = 1
return summa
Решето Эратосфена
Решето Эратосфена – это алгоритм предварительной обработки, который строит массив \(sieve\) , позволяющий для каждого целого числа от \(2\) до \(n\)эффективно определить, является ли оно простым. Если \(i\) простое, то \(sieve[i] = True\), иначе \(sieve[i] = False\).
Для построения массива алгоритм перебирает числа от \(2\) до \(n\). Обнаружив новое простое число \(i\), алгоритм помечает, что числа \(2i, 3i, 4i\) и т. д. не простые.
Работу решета можно значительно ускорить, если начинать зачёркивать числа, кратные \(p\), не с \(2p\), а с \(p^2\). Ведь числа \(2p, 3p, 5p, \ldots\) уже были зачёркнуты при обработке чисел \(2, 3, 5, \ldots\)
Ниже показана функция build_sieve, которая строит решето Эратосфена на отрезке \([0; n]\):
def build_sieve(n):
sieve = [True] * (n + 1)
sieve[:2] = False, False
for i in range(1, int(n ** 0.5) + 1):
if not sieve[i]:
continue
for j in range(i * i, n + 1, i):
sieve[j] = False
return sieve
При такой реализации алгоритм потребляет \(O(n)\) памяти и выполняет \(O(n \log \log n)\) действий.