欧几里得算法详解

2023-10-21 04:13| 来源: 网络整理| 查看: 265

欧几里得算法简介：

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b) 还有另一种求两数的最大公约数的方法是更相减损法。举例：假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：

1997 / 615 = 3 (余 152) 615 / 152 = 4(余7) 152 / 7 = 21(余5) 7 / 5 = 1 (余2) 5 / 2 = 2 (余1) 2 / 1 = 2 (余0)

至此，最大公约数为1 以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1

算法模板：

C版本

#include int Gcd(unsigned int M,unsigned int N) { unsigned int Rem; while(N > 0) { Rem = M % N; M = N; N = Rem; } return M; }

C++版本

int Gcd(int M,int N) { if(!N) return M; else return Gcd(N,M%N); } 欧几里得算法证明：

其计算原理依赖于下面的定理：定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。 gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0) 证法一因为a / b = k(余r)所以 a可以表示成a = kb + r（a，b，k，r皆为正整数，且r1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数≥cd，而非c，与前面结论矛盾】从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)，得证注意:两种方法是有区别的。辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的： ⒈.若 r 是 a ÷ b 的余数，且r不为0，则 gcd(a,b) = gcd(b,r) ⒉.a 和其倍数之最大公因子为 a。另一种写法是： ⒈.令r为a/b所得余数（0≤r

【本文地址】

公司简介

联系我们