辗转相除法求最大公约数

FSI

<P>用辗转相除法求两个数的最大公约数的步骤如下：<BR>先用小的一个数除大的一个数，得第一个余数；<BR>再用第一个余数除小的一个数，得第二个余数；<BR>又用第二个余数除第一个余数，得第三个余数；</P>
<P>这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。</P>
<P>例如求1515和600的最大公约数，<BR>第一次：用600除1515，商2余315；<BR>第二次：用315除600，商1余285；<BR>第三次：用285除315，商1余30；<BR>第四次：用30除285，商9余15；<BR>第五次：用15除30，商2余0。</P>
<P>1515和600的最大公约数是15。</P>
<P>辗转相除法是求两个数的最大公约数的方法。如果求几个数的最大公约数，可以先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数。这样依次下去，直到最后一个数为止。最后所得的一个最大公约数，就是所求的几个数的最大公约数。</P>
<P>以下是Python实现的代码 <BR></P>
<DIV class=quote>
<P>def mcd(a,b):<BR>    if a&lt;=0 or b&lt;=0:<BR>        return None</P>
<P>    v1,v2 = max(a,b), min(a,b)</P>
<P>    while v2:<BR>        v1, v2 = v2, v1%v2</P>
<P>    return int(v1)</P></DIV>

FSI

<P>转载递归方法</P>
<P>def Gba(a, b):<BR>    r = a%b<BR>    if r:<BR>        return b<BR>    else:<BR>        return Gba(b, r)<BR></P>