第38课 最大公约数
最大公约数（while循环、穷举、辗转相除法）
每次提到最小公倍数，总会让我想起另外一个概念，那就是最大公约数。最大公约数也称为最大公因数、最大公因子，是指两个或多个整数中能够整除它们的最大正整数。换句话说，最大公约数是能够同时整除给定整数的最大整数。
对比学习
例如：12和18的最大公约数是6。
温故知新
你可否记得在求最小公倍数时，我们采用了一种算法，从最大数开始+1，寻找最小公倍数。
试试逆向思维
求最大公约数，是不是可以从最小数开始-1来寻找呢？
（1）求出小数，gcd=(num1<num2)? num1 : num2，如果num1
（2）确定符合公约数的条件，同时满足整除给定的整数。用逻辑与符号（&&）连接num1 % gcd==0和num2 % gcd==0。
（3）从最小数开始-1，确保最先满足条件的是最大公约数。
试着完成程序。
运行程序：
请输入第一个正整数：12
请输入第二个正整数：18
最大公约数为：6
求最小公倍数是从大数开始+1，从小到大，一个一个地尝试；求最大公约数从小数开始-1，从大到小，一个一个地尝试。
提出思考
有没有更高效的算法呢？
当然有，可以试一试用辗转相除法求最大公约数。
先用两个数中较大的数除以较小的数，如果有余数，则用较小的那个数继续除以余数，按照这样的方法一直除下去，除到余数为0为止。最后的除数就是两个数的最大公约数。
辗转相除法
运行程序：
请输入两个整数: 12 18
最大公约数是: 6
while循环一直执行直到num2的值为0。在循环的每次迭代中，程序计算num1除以num2的余数并将结果存储到temp变量中；然后，num1被赋
值为原来的num2，而num2被赋值为temp。这个过程就是辗转相除法的关键，它不断用较小的数除以余数，直到余数为0。当余数为9时，此时num1的值就是最大公约数。
划重点
辗转相除法的核心就在于这段循环程序，一起来拆解一番吧！
按照辗转相除法的规则，将程序一行行拆解。
（1）先用两个数中较大的数除以较小的数。
程序直接使用num1 % num2，似乎并没有先计算出大数。那是因为只要进入循环就可以转变成大数除以小数。
试试看，假设num1=12为小数，num2=18为大数。
（2）如果有余数，则用较小的那个数继续除以余数，按照这样的方法一直除下去，除到余数为0为止。
这句规则可以拆分为以下两步：
①如果有余数，则用较小的那个数继续除以余数，按照这样的方法一直除下去，除到余数为0为止。
使用while(num2 !=0){}判断最终余数是否为0，如果不为0，则继续循环。
②如果有余数，则用较小的那个数继续除以余数，按照这样的方法一直除下去，除到余数为0为止。
temp=num1 % num2;→求余数运算得到余数temp num1=num2;→将小数num2赋值给num1
num2=temp;→将余数temp赋值给num2
这样num1变成了较小的那个数，num2变成了余数，再次执行循环体，num1 % num2就是较小数除以余数了。这段代码嵌套在循环体内，一直计算直到余数为0。
（3）最后的除数就是两个数的最大公约数。
余数为0，结束循环。cout<<"最大公约数是:"<<num1<<endl输出num1为最大公约数。
可是余数是num2呀，为什么会输出num1呢？
因为代码按照顺序执行，在结束循环前执行了以下操作：
num1=num2;
num2=temp;
num1的值变成了num2，而num2的值却成了temp。
遇到复杂的编程题不用着急，按照算法规则一步一步地拆解，一句一句地实现。
探索思考——裁纸的辗转相除
有一张长方形的纸，长是50厘米，宽是20厘米，要把它裁成若干个大小相同的正方形，并要使正方形的边长尽可能大且纸张没有剩余，正方形边长应是多少厘米?
一起来感受一下裁纸的辗转相除。
纸张不能有剩余，也就是裁成的正方形的边长既是长方形长的约数，又是长方形宽的约数，也就是长方形长和宽的公约数。
（1）将宽20厘米作为最大边尝试裁剪，还有剩余。
相当于将较大数除以较小数（50÷20），得到两个边长为20厘米的正方形，余10厘米。
（2）对剩余纸张，继续将较短的边作为正方形的最大边进行裁剪。
即20÷10的商为2，余数为0，得到两个边长为10厘米的正方形，没有剩余。
最终裁剪无剩余的最大正方形边长为10厘米，那么50和20的最大公约数就是10了。
巩固练习
（1）下面哪个C++程序段能够计算两个整数的最大公约数？（）
A．
while(num2 !=0){
temp=num1 % num2; num1=num2; num2=temp;}
B．
while(num2 !=1){
temp=num1 % num2; num1=num2; num2=temp;}
C．
while(num2 !=0){
temp=num1 % num2; num1=temp; num2=num1;}
D．
while(num2>0){
temp=num1 % num2; num1=num2; num2=temp;}
（2）阅读以下代码，填写程序运行的输出结果。
输出：
（3）通过计算两个整数的最大公约数，可以确定它们是否互质，即它们没有共同的除数（除了1）。请编写一个C++程序，接收用户输入的两个整数，并使用辗转相除法来计算它们的最大公约数。然后，根据最大公约数是否为1，判断这两个整数是否互质，并输出相应的信息。
编写的程序需要包括以下步骤：
1提示用户输入两个正整数。
2使用辗转相除法来计算这两个正整数的最大公约数。
3判断最大公约数是否为1，如果是，则输出“这两个整数是互质的。”；如果不是，则输出“这两个整数不是互质的。”。
4最后，输出“最大公约数的值：X”。
示例1：
请输入两个正整数：15 5
这两个整数不是互质的。
最大公约数的值：5
示例2：
请输入两个正整数：3 5
这两个整数是互质的。
最大公约数的值：1