Делитель числа

Целое число \(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)\) действий.

Практические задания