欧几里得算法

现在，我们来学习一下欧几里得算法。

欧几里得算法又称辗转相除法，主要用于算求两个正数之间的最大公约数。对于最大公约数这个名称，其英文名称为(Greatest Common Divisor)，故下面就用 gcd 来表示最大公约数的代称。

百度百科上定义：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

附上代码:

ll gcd(ll a, ll b)

{

	if (!b)

		return a;

	else

		return gcd(b, a % b);

}

//递归版本

ll gcd(ll a, ll b)

{

    ll t;

    while(b)

    {

        t=b;

        b=a%b;

        a=t;

    }

    return a;

}

//迭代版本

巴特西

GCD 代码以及GCD思想

欧几里得算法

最新文章

热门文章