Делимость, простые числа и основная теорема арифметики

С чего начинается олимпиадная математика: делимость, простые числа и теорема, которая делает арифметику предсказуемой.

Делимость: целое a делится на целое b ≠ 0 (пишут b | a), если существует целое k такое, что a = b·k.

Зачем это в олимпиадах

Почти любая задача по теории чисел на Codeforces, в USACO или на ВсОШ опирается на три кирпича: понимание делимости, простых чисел и разложения на множители. «Сколько делителей у числа», «сократите дробь», «найдите количество пар с заданным НОД», «проверьте, можно ли разбить отрезок на равные части» — всё это формулируется через делимость. Если эти основы лежат криво, более сложные темы (модулярная арифметика, комбинаторика по простому модулю, китайская теорема об остатках) построить не получится. Поэтому начнём с фундамента и сразу свяжем его с кодом.

Делимость: интуиция и свойства

Интуитивно «a делится на b» значит, что a предметов можно разложить на кучки ровно по b штук без остатка. Формально b | a означает a = b·k для некоторого целого k. Из определения мгновенно вытекают свойства, которыми вы будете пользоваться не задумываясь:

• Если b | a и c | b, то c | a (транзитивность).
• Если d | a и d | b, то d | (a + b) и d | (a − b), а вообще d | (x·a + y·b) для любых целых x, y. Это линейная комбинация — ключ к алгоритму Евклида.
• 1 | a всегда, и a | 0 для любого a ≠ 0 (ноль делится на всё).

Деление с остатком — другая опора. Для любых целых a и b > 0 существует единственная пара q (частное) и r (остаток), такая что a = b·q + r и 0 ≤ r < b. В Python это операторы // и %, причём Python гарантирует неотрицательный остаток при положительном делителе — это удобно и избавляет от багов, которые мучают писавших на C++.

a, b = 17, 5
q, r = a // b, a % b
print(q, r)            # 3 2, потому что 17 = 5*3 + 2
print(b * q + r == a)  # тождество деления с остатком

# Важная особенность Python: остаток неотрицателен при b > 0
print(-17 % 5)         # 3, а НЕ -2 как в C/C++
print(-17 // 5)        # -4 (округление вниз)

Вывод:

3 2
True
3
-4

Простые числа

Простое число — натуральное число p > 1, у которого ровно два натуральных делителя: 1 и само p. Числа с большим числом делителей называются составными. Единица не простая и не составная — это соглашение, без которого ломается единственность разложения.

Как проверить, что число простое? Наивно — перебрать все делители от 2 до n−1. Но есть ключевое наблюдение: если n = a·b и оба множителя больше √n, то a·b > n — противоречие. Значит хотя бы один делитель не превосходит √n. Поэтому достаточно проверять делители до √n — это снижает сложность с O(n) до O(√n).

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:   # эквивалент d <= sqrt(n), но без float
        if n % d == 0:
            return False
        d += 1
    return True

print([n for n in range(2, 30) if is_prime(n)])
print(is_prime(1_000_000_007))  # популярный олимпиадный модуль

Вывод:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
True

Обратите внимание на d * d <= n вместо d <= n ** 0.5. Сравнение целых точное, а вычисление квадратного корня в плавающей точке может дать 4.999999 вместо 5 и пропустить делитель. На олимпиаде такие мелочи решают исход.

Основная теорема арифметики

Основная теорема арифметики (ОТА): любое натуральное число n > 1 единственным образом (с точностью до порядка множителей) разлагается в произведение простых: n = p₁a₁ · p₂a₂ · … · pₖaₖ.

Эта теорема — почему теория чисел вообще работает. Она говорит, что у каждого числа есть единственный «генетический код» из простых. Существование разложения интуитивно: берём любой делитель, разбиваем, повторяем. Единственность тоньше и опирается на лемму Евклида: если простое p делит произведение a·b, то p делит a или p делит b. Из ОТА сразу следует, например, что √2 иррационален, а количество делителей числа определяется только показателями степеней (об этом — в третьем уроке).

def factorize(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:        # остался один большой простой множитель
        factors[n] = factors.get(n, 0) + 1
    return factors

print(factorize(360))      # 360 = 2^3 * 3^2 * 5
print(factorize(1_000_003))  # простое: один множитель в степени 1

Вывод:

{2: 3, 3: 2, 5: 1}
{1000003: 1}

Заметьте трюк if n > 1 после цикла: если после выноса всех маленьких множителей осталось число больше 1, это обязательно простое (иначе у него был бы делитель не больше √n, который мы бы уже вынесли). Так мы корректно ловим один крупный простой множитель, не перебирая до самого n.

Разбор задачи: сколько нулей в конце n!

Классический вопрос на делимость: сколькими нулями оканчивается n!? Ноль в конце — это множитель 10 = 2·5. Двоек в разложении факториала всегда больше, чем пятёрок, поэтому число нулей равно числу множителей 5. А степень, в которой 5 входит в n!, даёт формула Лежандра: ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … — считаем кратные 5, потом дополнительно кратные 25 (у них две пятёрки) и так далее.

def trailing_zeros(n):
    count = 0
    p = 5
    while p <= n:
        count += n // p     # кратные p добавляют по одной пятёрке
        p *= 5
    return count

print(trailing_zeros(100))    # 100! оканчивается на ... нулей
print(trailing_zeros(25))
# проверка прямым подсчётом для небольшого факториала
import math
def brute(n):
    f = math.factorial(n)
    c = 0
    while f % 10 == 0:
        c += 1
        f //= 10
    return c
print(brute(100), brute(25))

Вывод:

24
6
24 6

У 100! ровно 24 завершающих нуля, у 25! — 6. Формула совпала с честным подсчётом, но работает за O(log₅ n) и применима к гигантским n, где сам факториал не вычислить. Это типичная задача «на делимость через подсчёт степени простого» — частный случай формулы Лежандра, которая считает степень любого простого p в n!.

Подводные камни

• Граница перебора. Пишите d * d <= n, а не d < sqrt(n): квадраты простых (например n = 49) легко потерять из-за неточности float.
• Единица и ноль. is_prime должна отбрасывать n < 2. Забытый случай n = 1 — классический WA.
• Переполнение — не про Python. В C++ d * d для больших d переполняет int. В Python целые длинные (bignum) и не переполняются никогда — это его суперсила для теории чисел. Но помните об этом, когда переносите решение на C++.

Итог

• Делимость задаётся через a = b·k; делитель сохраняется при сложении и линейных комбинациях.
• Простоту проверяем перебором делителей до √n за O(√n), сравнивая d*d <= n.
• Основная теорема арифметики даёт единственное разложение на простые — фундамент всей теории чисел.
• Разложение факторизуется за O(√n) с трюком «остаток больше 1 — это простое».