134

Разложение на множители при поиске НОД (a, b) гораздо эффективнее, чем поиск делителей вплоть до меньшего из двух чисел a и b. Поиск простых множителей числа a потребует самое большее операций деления. Это значительное усовершенствование первоначального алгоритма, но в случае стозначных чисел даже наш новый метод становится уже чертовский сложной задачей.