广州 网站建设公司百度问一问付费咨询

题目描述

输入两个正整数a,b,求a,b的最大公约数。

输入

输入正整数a和b,中间用空格隔开

输出

输出最大公约数

样例输入

144 84

样例输出

12

程序分析 ：运用辗转相除法（欧几里得算法）

1. 用较大数除以较小数，取余数；
2. 用除数作为新的被除数，余数作为新的除数，重复步骤1，直到余数为0；
3. 最后一个非零余数即为最大公约数。

#include <stdio.h>
int main()
{int a,b,c;scanf("%d%d",&a,&b);c=a%b;while(c!=0){a=b;b=c;c=a%b;} printf("%d",b);return 0;
}