Нахождение НОД⁠⁠

Тут несколько моментов:
1) в школе помимо НОД проходят ещё и признаки делимости. При определённом опыте разложение числа на простые множители не составляет труда. Если речь, конечно, идёт о числах из задач, которые рассматривают в школе, а не из тех, что используют в криптоалгоритмах.
Кроме того, задача разложения на простые множители интересна сама по себе, поэтому её так же изучают. А раз уж изучили, то грех ей не пользоваться.
2) разложение на простые множители  необходимо не только в поиске НОДа. Например, НОК с помощью алгоритма Евклида вы не найдёте.
3) Есть куча примеров, когда применение алгоритма Евклида будет существенно длиннее поиска простых множителей. Скажем, возьмём числа 23 и 1124000727777607680000. "Разложив" 23 на множители (т.е. узнав, что это простое число, для тех, кто раньше этого не знал), мы обнаружим, что достаточно проверить, делится ли второе число на 23, а не искать все его простые множители. И не применять алгоритм Евклида. К слову, это число - 22! (и оно может быть так и написано в задачнике), соответственно, мы определяем НОД = 1 просто устно.
4) Алгоритм Евклида имеет две формы (с вычитанием и с делением с остатком). Большинство школьников почему-то если и усваивают, то только первый вид. Из-за чего мы возвращаемся к необходимому числу действий.