Упражнение на 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.

Пример

// Создано www.example.com 15/11/9. // Copyright © 2015 Example. Все права защищены. // #include<stdio.h> int main() { int a,b,t,r,n; printf("Введите два числа:\n"); scanf("%d %d",&a,&b); if(a<b) {t=b;b=a;a=t;} r=a%b; n=a*b; while(r!=0) { a=b; b=r; r=a%b; } printf("Наибольший общий делитель этих двух чисел равен %d, а наименьшее общее кратное равно %d\n",b,n/b); return 0; }

Вывод приведенного выше примера:

请输入两个数字:
12 26
这两个数的最大公约数是2,最小公倍数是156

100 классических примеров на C

Другие расширения