巳知:两个数的最大公约数求解的欧几里得算法如下:

利用被除数=商×除数+余数（在两个数中，取被除数大于除数），在算得第一个具体的被除数=商×除数+余数后，其中的除数就作为下一个具体的被除数=商×除数+余数的被除数，余数就作为除数，以后的具体的被除数=商×除数+余数就不断重复上述方法，直到余数为0为止，那么这时的除数就是最大公约数.

例.求1970与1066的最大公约数.

解:1970=1×1066+904

1066=1×904+162

904=5×162+94

162=1×94+68

94=1×68+26

68=2×26++16

26=1×16+10

16=1×10+6

10=1×6+4

6=1×4+2

4=2×2+0

所以，1970与1066的最大公约数为2.

现在讲改进的欧几里得算法.只是将欧几里得算法中的“余数”换为“min【余数，除数-余数】”即可.比较式的计算非常简单，其计算量相对于求出具体的被除数=商×除数+余数的计算量几乎忽略不计.

对上一个例题，改进的欧几里得算法如下:

1970=1×1066+904

（min【904，1066-904】=min【904，162】=162）

1066=6×162+94

（min【94，162-94】=68）

162=2×68+26

（min【26，68-26】=26）

68=2×26+16

（min【16，26-16】=10）

26=2×10+6

（min【6，10-6】=4）

10=2×4+2

（min【2，4-2】=2）

4=2×2+0

所以，最大公约数当然就是欧几里得算法所算得最大公约数的结果.

用欧几里得算法是11个具体的被除数=商×除数+余数，而用改进的欧几里得算法只有7个.