辗转相除法(Euclidean algorithm)
辗转相除法是历史上最著名的演算法之一,是求两数的 最大公因数(GCD) 极快速的方法.
维基百科 - 辗转相除法
原理是两个数字互相减来减去,最后就会剩下构成两个数字的共通单位,也就是 最大公因数.
图片来源:昌爸工作坊
[输入说明]
两个正整数a,b
[输出说明]
两数的最大公因数
code 1.0 - 模拟纸上的运算
总是拿较大的数除以较小的数
当其中一数变成0,另外一个数就是最大公因数
int a, b;
while( cin >> a >> b )
while( a!=0 and b!=0 )
if( a >= b )
a = a%b;
else if(