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

Школу закончил уже давно. И даже не помнил аббревиатуру - общий делитель "наибольший" или "наименьший". Сейчас поинтересовался у сына пятиклассника что они проходят - эти самые НОД и НОК. Решил проверить как он усвоил. Оказалось очень хреново. Стали разбираться.
Находят этот НОД по тому самому алгоритму разложением на простые множители в столбик (по которому и я когда-то в школе раскладывал). И тут я малость офигел. "Постой-постой", говорю, "а как вы простые множители находите?" Потому что понимаю - что разложение на простые множители это же нифига не тривиальная задача. На этом современные алгоритмы шифрования построены. Ну оказалось что последовательно пробует делить на натуральные числа (на самом деле надо же на простые) по возрастающей. Я говорю "и до каких пор ты пробуешь перебирать?". "Ну..."

Ну понятно. Дал ему для проверки разделить 169 - уже коллапс.
Вопрос - это сколько лет уже школьникам вдалбливают решение одной задачи через тупой перебор решений гораздо более сложной задачи? Есть же чуть более сложный (для небольших чисел), но корректный алгоритм Эвклида.