一、什么是公约数？
公约数，就是能同时整除几个整数的整数。最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。
例如： 2能整除4，2能整除8；4能整除4，4能整除8，所以说(2和4)是(4和6)的公约数，而4是(2和4)的最大公约数。
二、求解两个数的最大公约数
🍑1、枚举法
思路： 假设两个数字a和b，比较出更小的数字赋值给变量min，遍历1到min的整数，找到所有能共同被a和b整除的数字，其中数值最大的便是所求最大公约数。
📝代码展示
//枚举法 #include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d %d",&a,&b); int min = (a < b ? a : b); while (a % min != 0 || b % min != 0)//如果不能同时整除 { min--; } printf("%d",min); return 0; }
🍑2、相减法
思路： 假设两个数字a和b，如果a>b，则a=a-b;如果b>a,则b=b-a。一直循环计算直到a=b，则此时a、b的值即为所求最大公约数。
📝代码展示：
//相减法 #include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d %d",&a,&b); while (a != b)//直到两个数相等 { if (a > b) { a = a- b; } else { b = b - a; } } printf("%d",a); return 0; }
🍑3、辗转相除法
思路： 假设两个数字a和b，求两个数字相除的余数c=a%b，如果余数为0，则b为最大公约数。如果b不为零，a=b,b=c,继续循环计算。
📝代码展示：
//辗转相除法 #include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d %d",&a,&b); while (a%b != 0)//如果不能整除 { int c = a % b; a = b; b = c; } printf("%d",b); return 0; }
📖总结
- 三种方法穷举法效率最低
- 推荐使用辗转相除法和相减法
