Алгоритм для поиска НОК

[Евгений Машеров]

INGELRII в сообщении #1103685 писал(а):

Насчет алгоритмов умножения быстрее, чем школьный метод умножения одного числа на цифры другого и последующего суммирования строк (и как частный случай, двоичного варианта этого же метода), прочитать можно там же; я был в шоке, когда узнал.

Да есть они, есть, и Карацуба, и Шенхаге-Штрассен. Только они для длинных чисел. Карацуба для чисел длинее 320-640 бит лучше обычного, Шёнхаге-Штрассен лучше Карацубы для десяти тысяч десятичных знаков. А тут что-то для достаточно малых предполагается.

[venco]

Ещё можно заметить, что для таких больших чисел разница между умножением и делением становится несущественной.

[bondkim137]

А для маленьких, в современных реалиях (при аппаратной поддержке), она впринципе небольшая и может быть съедена доп. расходами на 'расширение' алгоритма Евклида. Особенно, если учесть конвеерную архитектуру процессоров и не пользоваться результатом деления сразу.
(но идея отличная)