Поиск делителей и НОД/НОК

Зачем это в ЕГЭ. Задание 25 (высокий уровень сложности, 2 первичных балла). Проверяет умение анализировать алгоритмы с циклами и условиями, работающие с делителями чисел. Встречается в 30% реальных вариантов.

Главная идея. Для эффективного поиска делителей используем перебор до корня из числа. НОД и НОК вычисляются через алгоритм Евклида или разложение на простые множители. Ключ — оптимизация перебора и учёт парных делителей.

Алгоритм (чеклист).
1. Для поиска всех делителей N перебираем числа от 1 до $\sqrt{N}$.
2. Если i делит N, то добавляем в список и i, и N/i (кроме случая i = N/i).
3. Для НОД(a,b): пока b ≠ 0, заменяем (a,b) на (b, a mod b). Результат — последний ненулевой остаток.
4. Для НОК(a,b): используем формулу $НОК(a,b) = \frac{a \cdot b}{НОД(a,b)}$.
5. Проверяем граничные случаи (N=1, a=0 и т.п.).

Опоры (кратко).
- Основная теорема арифметики: любое число единственным образом раскладывается на простые множители.
- $НОД(a,b) = НОД(b, a \mod b)$ (алгоритм Евклида).
- $НОК(a,b) \cdot НОД(a,b) = a \cdot b$.
- Если $N = p_1^{k_1} \cdot ... \cdot p_m^{k_m}$, то число делителей равно $(k_1+1)\cdot...\cdot(k_m+1)$.

Пример 1 (поиск делителей).
Шаг 1. Дано N = 36. Инициализируем пустой список делителей.
Шаг 2. Перебираем i от 1 до $\lfloor \sqrt{36} \rfloor = 6$.
Шаг 3. i=1: 36%1=0 ⇒ добавляем 1 и 36.
Шаг 4. i=2: 36%2=0 ⇒ добавляем 2 и 18.
Шаг 5. i=3: 36%3=0 ⇒ добавляем 3 и 12.
Шаг 6. i=4: 36%4=0 ⇒ добавляем 4 и 9.
Шаг 7. i=6: 36%6=0 ⇒ добавляем только 6 (так как 6=36/6).
Результат: [1, 36, 2, 18, 3, 12, 4, 9, 6].

Пример 2 (НОД и НОК).
Шаг 1. Дано a=56, b=98.
Шаг 2. НОД: 56 mod 98=56 → (98,56).
Шаг 3. 98 mod 56=42 → (56,42).
Шаг 4. 56 mod 42=14 → (42,14).
Шаг 5. 42 mod 14=0 → НОД=14.
Шаг 6. НОК = (56×98)/14 = 392.

Типичные ошибки.
1. Перебор до N вместо $\sqrt{N}$ — резко снижает производительность.
2. Повторение парных делителей — при i = N/i нужно добавить только один делитель.
3. Неучёт НОД(0,a)=a — приводит к бесконечному циклу.
4. Путаница в формуле НОК — пытаются вычислить как (a+b)/2.

Дальше. Разбери задачи на нахождение чисел с заданным количеством делителей или взаимно простых пар.