本文主要是介绍C语言求两个数的最大公约数、最小公倍数（三种方法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最大公约数：也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。（如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数）
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
以两个整数为例，我们知道最小公倍数=两整数乘积 / 最大公约数。那么在求出最大公约数的基础下，利用该公式便可求出最小公倍数。
那么如何求两个数的最大公约数，最小公倍数呢？
法一：
我们通常是先比较两个数的大小，找到较小的一个。然后让这两个数都对 以较小数为首的递减序列（增量为-1） 求余，如果两个数同时都能被其整除，则找到最大公约数。
int main()
{int a = 17, b = 35;int n, i;//找a,b中较小的数if (a > b){n = b;}else{n = a;}for ( i = n; i > 0; i--){if (a%i == 0 && b%i == 0){printf("最大公约数为%d\n", i);printf("最小公倍数为%d\n", (a*b) / i);break;}}system("pause");return 0;
}
法二（辗转相减法）：
辗转相减法：不断地对两个数做减法，以此求出最大公约数。即用大数减小数，将所得结果保存到大数中；再用此时的大数减小数，将结果保存到大数中，如此重复，直到最后两数相等，便求出了最大公约数。
以求a = 24和b = 36的最大公约数为例，具体求解思路如下：
1. b=b-a=36-24=12;
2. a=a-b=24-12=12;
3.a=b = 12（此时两数相等） ---> 最大公约数为12
代码实现如下：
//辗转相减法求最大公约数,最小公倍数
int main()
{int a = 28, b = 40;int mul = a*b;while (a != b){if (a > b){a = a - b;}else if (a < b){b = b - a;}}printf("最大公约数为%d\n", a);printf("最小公倍数为%d\n", mul/a);system("pause");return 0;
}法三（辗转相除法）：
辗转相除法是求最大公约数的一种方法，其具体求解思路如下：
两数相除（不论大小），再用除数除以出现的余数（第一余数），再用第一余数除以出现的余数（第二余数），如此反复，直到最后余数是0为止，那么最后的除数便是这两个数的最大公约数。
以求24和50的最大公约数为例，具体求解步骤如下：
1. 24%50=24（余数不等于0）
2. 50%24=26（余数不等于0）
3. 24%26=24（余数不等于0）
4. 26%24=2（余数不等于0）
5.24%2=0（余数等于0） --->最大公约数为此时的除数2
代码实现如下：
#include <stdio.h>
#include <windows.h>
int main()
{int a = 24, b = 50;int tmp = 0;int mul = a*b;while (tmp = a%b){a = b;b = tmp;}printf("最大公约数为%d\n", b);printf("最小公倍数为%d\n", mul / b);system("pause");return 0;
}
这篇关于C语言求两个数的最大公约数、最小公倍数（三种方法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
