摘要：辗转相除法 公元前3世纪.欧几里得介绍了求两个正整数a,b的最大公约数的方法.求出一列数:.这列数从第三项开始.每一项都是前两项相除所得的余数(即).余数等于0的前一项.即是a和b的最大公约数.这种方法称为“欧几里得辗转相除法 . 例1 求两个正数8 251和6 105的最大公约数． (分析:8 251与6 105两数都比较大.而且没有明显的公约数.如能把它们都变小一点.根据已有的知识即可求出最大公约数) [解]8 251＝6 105×1+2 146 显然8 251和的2 146最大公约数也必是2 146的约数.同样6 105与2 146的公约数也必是8 251的约数.所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数． 6 105＝2146×2+1813 2 146＝1813×1+333 1 813＝333×5+148 333＝148×2+37 148＝37×4+0 则37为8 251与6 105的最大公约数． [小结]以上我们求最大公约数的方法就是欧几里得辗转相除法．其求最大公约数的步骤如下: 第一步:用较大的数除以较小的数,得到一个商和一个余数, 第二步:若.则为的最大公约数,若.则用除数除以余数,得到一个商和一个余数, 第三步:若.则为的最大公约数,若.则用除数除以余数得到一个商和一个余数, -- 依次计算直至.此时所得到的即为所求的最大公约数. [练习]求a=204.b=85的最大公约数.步骤为: S1 204÷85的余数为34. S2 85÷34的余数为17. S3 34÷17的余数为0. 所以它们的最大公约数为17. 算法描述:计算出a÷b的余数r.若r=0.则b为a.b的最大公约数,若r≠0.则把前面的除数b作为新的被除数.把余数r作为新的除数(a.b要重新赋值.a←b.b←r).继续进行上述运算.直到余数为0(用While循环语句.循环的执行条件是r≠0.当r=0时.循环终止).此时的除数即为所求的最大公约数. 算法如下: S1 输入两个正整数a,b, S2 若Mod(a.b)=0.则转S3,否则.r←Mod(a,b). a←b.b←r.转S2. S3 输出最大公约数b. [流程图] [伪代码]

网址：http://m.1010jiajiao.com/timu_id_2503493[举报]