Числовые алгоритмы — классика программирования и олимпиадной математики: наибольший общий делитель, простые числа, разложение на множители, целые решения уравнений. Их сила в том, что они работают быстро даже для больших чисел.
Что нужно знать
- Алгоритм Евклида: $\gcd(a, b) = \gcd(b, a \bmod b)$, $\gcd(a, 0) = a$.
- Расширенный Евклид находит $x, y$: $ax + by = \gcd(a, b)$.
- $\text{НОК}(a, b) = \dfrac{a \cdot b}{\text{НОД}(a, b)}$.
- Проверка простоты: делители достаточно искать до $\sqrt{n}$.
- Решето Эратосфена: вычёркивать кратные простого $p$ начиная с $p^2$, останавливаться при $p^2 > n$.
- Разложение на множители: делить на 2, 3, 5… пока делится; остаток > 1 — сам простой множитель.
- $ax + by = c$ имеет целые решения тогда и только тогда, когда $\gcd(a, b)$ делит $c$.
Где чаще всего ошибаются
- Перебирать делители до $n$ вместо $\sqrt{n}$.
- Начинать вычёркивание в решете с $2p$ (лишняя работа) или останавливаться слишком рано.
- Искать НОК перебором кратных для больших чисел.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 30 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.