用更相减损术求最大公约数时,它的步骤不是先判断是否为偶数吗?为什么在程序框图中没有显示出来,而是判断是否相等?

Question

用更相减损术求最大公约数时,它的步骤不是先判断是否为偶数吗?为什么在程序框图中没有显示出来,而是判断是否相等?

Answer 1

的确,按照“古典”的更相减损术求最大公约数时,是要先判断是否为偶数,若均为偶数,则均除以2,直到有奇数为止,这样做的好处是把数据规模减小.但是,如果用计算机来求最大公约数,这一步不仅显得多余（机器计算86-58与43-29是一样的难易程度）,而且最后求出最大公约数后,还要乘以刚才约掉的2的因数,显得更加繁琐,因此,用计算机来求最大公约数,往往都直接用大数减去小数,辗转相减.不过,求最大公约数最好的算法还是欧几里德算法（辗转相除法）,因为除法比减法效率要高得多.