１． 求两个正整数最大公约数的算法

学生通常会用辗转相除法求两个正整数的最大公约数：

例１：求７８和３６的最大公约数

（１） 利用辗转相除法

步骤：

计算出７８３６的余数６，再将前面的除数３６作为新的被除数，３６６＝６，余数为０，则此时的除数即为７８和３６的最大公约数。

理论依据： ，得与有相同的公约数

（２） 更相减损之术

指导阅读课本P----P，总结步骤

步骤：

以两数中较大的数减去较小的数，即７８－３６＝４２；以差数４２和较小的数3６构成新的一对数，对这一对数再用大数减去小数，即４２－３６＝６,再以差数６和较小的数３６构成新的一对数，对这一对数再用大数减去小数，即３６－６＝３０,继续这一过程,直到产生一对相等的数，这个数就是最大公约数

即，

理论依据：

由，得与有相同的公约数

算法：

输入两个正数；

如果，则执行，否则转到；

将的值赋予；

若，则把赋予，把赋予，否则把赋予，重新执行；

输出最大公约数

程序:

a=input("a=")

b=input("b=")

while a<>b

if a>=b

　　a=a-b;

　else

　 b=b-a

　end

end

print(%io(2),a,b)

例1 ：用等值算法（更相减损术）求下列两数的最大公约数。

（1）225，135 （2）98，280

例2：用辗转相除法验证上例中两数的最大公约数是否正确。