---
title: "Математика и теория чисел (НОД, решето, модульная арифметика)"
url: https://algopath.pro/ru/patterns/math-number-theory
language: ru
summary: "Теория чисел заменяет перебор всех значений обычной арифметикой. НОД, модульные правила и решето убирают полный перебор."
updated: 2026-08-24
---

# Математика и теория чисел (НОД, решето, модульная арифметика)

Теория чисел заменяет перебор всех значений обычной арифметикой. НОД, модульные правила и решето убирают полный перебор.

## Математика и теория чисел (НОД, решето, модульная арифметика): как это работает?

Правило Евклида заменяет пару чисел меньшей парой. НОД чисел a и b равен НОД чисел b и a по модулю b.

Он останавливается, когда второе число стало нулём. Ответом служит оставшееся число.

Наименьшее общее кратное следует из НОД. Это a умножить на b и поделить на их НОД.

Решето вычёркивает кратные каждого встреченного простого. Всё невычеркнутое является простым.

Модульная арифметика держит числа маленькими. Берите остаток после каждого шага, а не только в конце.

У деления простой модульной формы нет. Вместо него нужен обратный элемент по модулю.

- `нод(48, 18)` 48 по модулю 18 даёт 12.
- `нод(18, 12)` 18 по модулю 12 даёт 6.
- `нод(12, 6)` 12 по модулю 6 не даёт ничего.
- `нод(6, 0) = 6` Второе число стало нулём. Ответ равен 6.
- `нок = 48 на 18 делить на 6` Получается 144, и ни одно кратное не перечислялось.

## Математика и теория чисел (НОД, решето, модульная арифметика): когда применять?

- сократить дробь до несократимого вида
- перечислить все простые числа до n
- ответ по модулю 1e9+7
- когда снова совпадут два повторяющихся интервала (НОК)

## Математика и теория чисел (НОД, решето, модульная арифметика): с чем путают?

- **Битовые манипуляции** - Оба работают с самим числом. Та страница про отдельные биты.
- **Хеш-множество / словарь** - Множество простых чисел всё равно надо как-то построить. Решето и есть способ его построить.
- **Динамическое программирование (1-D)** - Формула отвечает сразу там, где динамика заполняет таблицу. Сначала поищите замкнутую форму.
- **Префиксные суммы** - Префиксные суммы отвечают по сохранённым значениям. Здесь ответ следует из свойств самих чисел.

## Математика и теория чисел (НОД, решето, модульная арифметика): сложность по времени и памяти

НОД стоит O(log от меньшего значения). Решето до 1e7 нормально, а до 1e9 уже нет.

## Математика и теория чисел (НОД, решето, модульная арифметика): разбор примера

### Посчитать простые числа меньше n

Посчитайте простые числа строго меньше n.

Проверять каждое число по отдельности слишком медленно при большом n.

Вычёркивайте все кратные каждого простого как составные.

Начинайте вычёркивать с квадрата простого. У всего меньшего уже есть меньший делитель.

```javascript
function countPrimes(n) {
    if (n < 3) return 0;

    const composite = new Array(n).fill(false);
    let count = 0;

    for (let p = 2; p < n; p++) {
        if (composite[p]) continue;
        count++;

        // start at p * p: everything smaller already has a smaller factor
        for (let multiple = p * p; multiple < n; multiple += p) {
            composite[multiple] = true;
        }
    }

    return count;
}
```

## Математика и теория чисел (НОД, решето, модульная арифметика): частые ошибки

- **Берут остаток только в конце** Значение переполнится задолго до этого. Уменьшайте его после каждого умножения.
- **Получают отрицательный остаток** В JavaScript минус один по модулю пять равен минус одному. Добавьте модуль и возьмите остаток снова.
- **Начинают внутренний цикл решета с удвоенного простого** У всего ниже квадрата простого уже есть меньший делитель. Такой старт тратит большую часть работы.
- **Проверяют делители дальше квадратного корня** Делитель выше корня всегда идёт в паре с делителем ниже. Останавливайтесь на корне.

## Математика и теория чисел (НОД, решето, модульная арифметика): задачи с собеседований

- **Наибольший общий делитель строк** Длина ответа это НОД двух длин.
- **Подсчёт простых чисел** Решето вместо проверки каждого числа.
- **Уродливые числа II** Три указателя по кратным 2, 3 и 5.
- **Степень тройки** Повторное деление или одна проверка делимости.
- **Дробь в периодическую десятичную** Повторившийся остаток и отмечает период.
- **Номер колонки в таблице** Система по основанию 26, но без нулевой цифры.
- **Счастливое число** Поиск цикла по суммам квадратов цифр.

## JavaScript

```javascript
function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
function lcm(a, b) {
    return (a / gcd(a, b)) * b;
}
```

## Python

```python
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b
```

## PHP

```php
function gcdEuclid(int $a, int $b): int {
    while ($b !== 0) {
        [$a, $b] = [$b, $a % $b];
    }
    return $a;
}
function lcm(int $a, int $b): int {
    return intdiv($a, gcdEuclid($a, $b)) * $b;
}
```