最大公约数 ——解题报告 作者：宋含章 七（12）班 1
题目：最大公约数 输入两个整数a和b，输出它们的最大公约数。 【输入样例】40 24 【输出样例】8 2
用辗转相除法求两个数的最大公约数的步骤如下： ①先用小的一个数除大的一个数，得第一个余数； ②再用第一个余数除小的一个数，得第二个余数； 1.欧几里得辗转相除法(gcd算法) 该算法的时间复杂度为O(log n) 辗转相除法是求两个数的最大公约数的方法。如果求几个数的最大公约数，可以先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数。这样依次下去，直到最后一个数为止。最后所得的一个最大公约数，就是所求的几个数的最大公约数. 用辗转相除法求两个数的最大公约数的步骤如下： ①先用小的一个数除大的一个数，得第一个余数； ②再用第一个余数除小的一个数，得第二个余数； ③又用第二个余数除第一个余数，得第三个余数； 这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。 3
eg.求1515和600的最大公约数. ①用600除1515商2余315； ②用315除600商1余285； ③用285除315商1余30； ④用30除285商9余15； ⑤用15除30商2余0. ∴1515和600的最大公约数是15. 4
a除以b,将余数赋给r,将b的值赋给a,将r的值赋给b， 直到r=0。 ③输出。 ②循环： a除以b,将余数赋给r,将b的值赋给a,将r的值赋给b， 直到r=0。 ③输出。 5
代码: var a,b,r:longint; begin readln(a,b); repeat r:=a mod b; a:=b; until r=0; writeln(a); end. 代码: 6
注意：枚举法只要枚举到n的算术平方根。 2.枚举法 从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。 注意：枚举法只要枚举到n的算术平方根。 7
代码： var n,i,k:integer; begin readln(n); for i:=1 to trunc(sqrt(n)) do if n mod i=0 then inc(k); k:=k*2; if trunc(sqrt(n))=sqrt(n) then dec(k); writeln(k); end. 8
The end 9 9