INGELRIIВы не учитываете что в реальной практике возможны и нередки случаи противоречия теоретическим оценкам, например умножение может быть
быстрее сложения ... (Пример: сложение и умножение вещественных чисел, сложение требует двух нормализаций, до и после, умножение лишь одной после, если нормализация выполняется дольше умножения, а такое вполне реально, матричные умножители никто не отменял, то налицо парадокс.) А во многих современных архитектурах умножение конечно медленнее сложения, но вовсе не так катастрофично, как следует из Кнута и теории алгоритмов. Просто потому, что его специально ускоряют, аппаратными методами. И заменять имеющуюся аппаратную команду даже самым лучшим и быстрым алгоритмом выгодно весьма редко.
По теме, я думаю алгоритм нахождения НОК будет не быстрее алгоритма НОД, а тогда добавка к НОД умножения и деления (которое можно в 60% случаев и не выполнять) не слишком заметна. Наверное. И как правильно сказали выше, уж точно не будет быстрее умножения.
Хотя ради спортивного интереса мне бы тоже хотелось взглянуть на алгоритм нахождения НОК без нахождения НОК и быстрее чем приведённый выше со сложениями.