12774: 【设计型】第7章:函数7.7(2) 欧几里得算法求最大公约数
Memory Limit:256 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:2
Solved:0
Description
两个正整数的最大公约数是能够整除这两个整数的最大整数。采用欧几里得算法编写计算最大公约数的函数Gcd(),在主函数中调用该函数计算并输出从键盘任意输入的两整数的最大公约数。
欧几里得算法:也称辗转相除法。对于正整数a和b,连续进行求余运算,直到余数为0为止,此时非0的除数就是最大公约数。设r=a mod b表示a除以b的余数,若r≠0,则将b作为新的a,r作为新的b,即Gcd(a,b)=Gcd(b,r),重复a mod b运算,直到r=0时为止,此时b为所求的最大公约数。例如,50和15的最大公约数的求解过程可表示为:Gcd(5015)=Gcd(155)=Gcd(5,0)=5。
Input
2个正整数。两数之间用逗号隔开。
Output
1个数。这个数是最大公约数。
Sample Input Copy
50,15
Sample Output Copy
5