第9节  用辗转相除法求两数的最大公约数

例：有一列数 

其中a ，b为已知正整数，且a>b ，从第三项开始，以后各项分别是前项除以后项所得的余数，该列数的最后一项是0，求这列数的倒数第二项，即a和b的最大公约数。此种求最大公约数的方法叫辗转相除法。

• 根据题目要求的方法设计的框图如下：

• 根据框图编写的程序如下：

CLS

INPUT “A ，B=”；A ，B

IF  A<B THEN  T=A ：A=B ：B=T

A1=A ：B1=B　　 　（用A1和B1分别保存A和B的值）

C=A  MOD  B　　　　（A和B的余数赋给C做为第三项）

DO  WHILE  C<>0 　 （若余数为0退出循环）

   A=B ：B=C

   C=A  MOD  B

LOOP

PRINT “GCD(”;A1;B1;“)=”;B     (输出a和b的最大公约数）

END