FSI 发表于 2005-11-29 19:12

辗转相除法求最大公约数

<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 发表于 2005-12-2 17:02

<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>
页: [1]
查看完整版本: 辗转相除法求最大公约数