Упражнение на C, пример 16 — наибольший общий делитель и наименьшее общее кратное
100 классических примеров на C
Заголовок:Введите два положительных целых числа m и n и найдите их наибольший общий делитель и наименьшее общее кратное.
Анализ программы:
(1) Наименьшее общее кратное = произведение двух введённых чисел, делённое на их наибольший общий делитель; ключевым является нахождение наибольшего общего делителя.
(2) Используйте алгоритм Евклида (также известный как алгоритм Евклида) для нахождения наибольшего общего делителя.
1) Доказательство: пусть c — наибольший общий делитель a и b, обозначаемый как c = gcd(a, b), a >= b.
Пусть r=a mod b
Пусть a = kc, b = jc, тогда k и j взаимно просты; иначе c не был бы наибольшим общим делителем.
Из вышесказанного, r=a-mb=kc-mjc=(k-mj)c
Видно, что r также кратен c, а k - mj и j взаимно просты; иначе это противоречит предыдущему факту, что k и j взаимно просты.
Таким образом, видно, что наибольший общий делитель b и r также равен c, т.е. gcd(a,b)=gcd(b,a mod b). Доказано.
2) Описание алгоритма:
Шаг 1: a ÷ b, пусть r — полученный остаток (0 ≤ rШаг 2: Обмен: присвоить a←b, b←r и вернуться к шагу 1.
Пример
Вывод приведенного выше примера:
请输入两个数字: 12 26 这两个数的最大公约数是2,最小公倍数是156Другие расширения