Метод: евклидов алгоритм. Причина: он работает на целых без факторизации, даёт НОД быстро, а НОК находят по формуле $\mathrm{lcm}(a,b)=\frac{|ab|}{\gcd (a,b)}$.
Короткое численное решение:
- $987654321=8\cdot 123456789+9$, значит $\gcd (123456789,987654321)=\gcd (123456789,9)=9$.
- $\gcd (123456789,987654321)=9$.
- $\mathrm{lcm}(123456789,987654321)=\frac{123456789\cdot 987654321}{9}=\frac{121932631112635269}{9}=13548070123626141$.
Почему оптимален и сложность:
- Евклидов алгоритм требует $O(\log \min (a,b))$ шагов деления (количество итераций линейно по числу разрядов в двоичном представлении — точнее $O(n)$ итераций где $n$ — число бит, но обычно оценивают как $O(\log \min (a,b))$).
- Битовая сложность зависит от стоимости деления/умножения: при школьном умножении/делении $M(n)=O(n^2)$ (где $n$ — число бит) общая сложность $O(n^2\log n)$. С быстрыми алгоритмами умножения получается $O(M(n)\log n)$.
- Факторизация чисел вообще сложнее (экспоненциально в наихудшем случае при текущих классических алгоритмах), поэтому для НОД/НОК евклидовый алгоритм практически оптимален.