最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
为大家带来找最大公约数的两种办法，1.暴力求解法，2.辗转相除法，3，更相减损法
一、暴力求解法
#include <stdio.h> int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n);//24 18 int max = 0; //假设最大公约数max就是m和n的较小值 if (m > n) max = n; else max = m; while (1) { if (m % max == 0 && n % max == 0) { printf("最大公约数就是：%d\n", max); break; } max--; } return 0; }
二、辗转相除法
欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数.
辗转相除法 int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n); int t = 0; while (t=m%n) { m = n; n = t; } printf("最大公约数：%d\n", n); return 0;
- 辗转相除法相较于暴力求解法更加高效。
三、更相减损法
更相减损法：更相减损术， 出自于中国古代的《九章算术》，也是一种求最大公约数的算法。
①先判断两个数的大小，如果两数相等，则这个数本身就 是就是它的最大公约数。
②如果不相等，则用大数减去小数，然后用这个较小数与它们相减的结果相比较，如果相等，则这个差就是它们的最大公约数，而如果不相等，则继续执行②操作。
int main() { int a = 0; int b = 0; scanf("%d,%d,&a,&b); if (a == b) { return a; } else if (a > b) { return divi_2(a - b, b); } else { return divi_2(b - a, a); }
