辗转相除法得最大公因数 C语言

辗转相除法得最大公因数 C语言

首先放出代码

int gcd(int a, int b) 
{
	if(a%b == 0) return b;
	else return gcd(b, a%b);
}

        辗转相除是将a与b相除得到余数k，如果余数k==0则返回值b，如果k不为0则将 除数b 与 k 相除，再判断第二次的余数k2是否为零，如此反复，故为辗转相除。

        其实现原理：

        举个例子，求30与21的最大公因数。假设最大公因数为x，那么30%x == 0, 21%x == 0,

故（30-21）%x == 0（将30拆为 21 与 9， 21 % x == 0， 所以 9 % x == 0）。继续，21中有两个9，21 - 9*2 = 3， 所以 3%x == 0。因为 9%3 == 0 所以3就是最终结果。

        其实就是将一个 较大的数（x的倍数）中若干个 较小的数（依然是x倍数）剔除，剩下的部分依然是 x的倍数，然后一直进行剔除步骤，直到无法继续剔除，最后的值就是我们需要的最大公因数。