P10516: 穷举法求最大公约数
传统题
1.000s
时间限制
256MB
内存限制
54 提交
28 解决
【题目描述】
两个正整数的最大公约数是能够整除这两个整数的最大整数。采用穷举法编写计算最大公约数的函数
Gcd()，在主函数中调用该函数计算并输出从键盘任意输入的两整数的最大公约数。
穷举法：由于
a和b的最大公约数不可能比a和b中的较小者还大，否则一定不能整除它，因此，先找到a和b中的较小者t，然后从t开始逐次减1尝试每种可能，即检验t到1之间的所有整数，第一个满足公约条件的t，就是a和b的最大公约数。
【输入】
2个正整数。两数之间用逗号隔开。
【输出】
1个数。这个数是最大公约数。