大家好，又见面了，我是你们的朋友全栈君。
求两个数的最大公约数的常用方法：
※“辗转相除法”，又名欧几里得算法。基本方法如下：
设两数为a和b(a>b)，用a除以b，得a÷b=q……r，若r=0 ，则最大公约数为b；若r≠0 ,则再用b÷r，得b÷r=q……r’，若r’=0，则最大公约数为r’，若r’≠0，则继续用r÷r’……直到能够整除为止，此时的除数即为最大公约数。
例如：a=99，b=18。a÷b=99÷18=5……9不能整除，则继续b÷r=18÷9=2可以整除，则此时的除数9即为a和b两数的最大公约数。
①代码如下：
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
int t = 0;
scanf("%d%d", &a, &b);//99,18
while (a%b != 0){
t = a%b;
a = b;
b = t;
}
printf("最大公约数为：%d\n", b);
return 0;
}首先，从键盘键入两个数a和b的值，变量t来保存余数。用while循环来判断能否整除，根据“辗转相除法”，先用第一个数a÷b再将除数b赋给a，余数赋给b，循环往复，直到能整除时结束循环，此时的除数b即为最大公约数。
（特别说明：若a<b，例如a=18，b=99。t=a%b=18；a=99；b=t=18。我们发现通过一次循环交换了a、b的值，这时就能满足a>b的条件了，在继续根据辗转相除的方法即可得到最大公约数。）
※拓展：求两个数的最小公倍数
关于最小公倍数与最大公约数，有这样的定理：最小公倍数×最大公约数=两数的乘积。
即：最小公倍数=两数的乘积÷最大公约数
②代码如下：
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
int t = 0;
scanf("%d%d", &a, &b);//18 99
int m = a;
int n = b;
while (a%b != 0){
t = a%b;//余数 9
a = b;//18
b = t;//9
}
printf("最大公约数为：%d\n", b);//9
printf("最小公倍数为:%d\n",m*n/b);
return 0;
}首先，从键盘键入两个数a和b的值，变量t来保存余数。再设两个变量m、n来保存a、b的原值。
先根据辗转相除法求出最大公约数b’（过程同①），再由最小公倍数=两数的乘积÷最大公约数=m×n÷b’求得最小公倍数。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/145408.html原文链接：https://javaforall.net
