c语言编程,利用辗转相除法求公约数

Python015

c语言编程,利用辗转相除法求公约数,第1张

辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。

其原理如下：

设两数为a、b(b<a)，用gcd(a,b)表示a，b的最大公约数，r=a (mod b) 为a除以b以后的余数，k为a除以b的商，即a÷b=k.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r）。

第一步：令c=gcd(a,b），则设a=mc，b=nc

第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c

第三步：根据第二步结果可知c也是r的因数

第四步：可以断定m-kn与n互质【否则，可设m-kn=xd，n=yd (d>1)，则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)。

证毕。

以上步骤的操作是建立在刚开始时r!=0的基础之上的。即m与n亦互质。

按照其规则，C语言实现如下：

int GCD(int a,int b)

{return b==0？a:GCD(b,a%b)；}

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

下面是一个使用C语言的实现：

intexGcd(int a,int b,int &x,int &y)

{

    if(b==0)    //当b==0时，得到解

    {

        x=1y=0

        return a

    }

    intr=exGcd(b,a%b,x,y)//递归调用自身，求解

    intt=xx=yy=t-a/b*y

    return r

}

就是把上一轮有余数的除法计算中，

除数变为下一轮计算的被除数，

余数变为下一轮计算的除数，

一直这样计算下去，

直到最后一次计算余数为零，

在最后一轮计算中的被除数，即为所求的最大公约数。

举例：

105和85的最大公约数

第一轮计算

105÷85=1...20

第二轮计算

85÷20=4...5

第三轮计算

20÷5=4

第三轮没有余数，

因此

105和85的最大公约数就是第三轮计算的被除数

5.

至于C语言编程，下边是我自己写的G函数(思想就是辗转相除法求最大公约数)

int

G(int

x,int

y)

{

int

t

while(y!=0)

{

t=x%y

x=y

y=t

}

return

x

}