求公约数公因数c语言

### C语言求最大公约数算法示例 以下是几种常见的C语言实现求最大公约数的算法： #### 方法一：穷举法 这种方法通过从两数中的较小者开始逐步减少，找到能同时整除两个数的最大值。 ```c #include<stdio.h> int main() { int m, n, t; printf("请输入两个数:"); scanf("%d%d", &m, &n); if (m > n) t = n; else if (m < n) t = m; while (1) { if (m % t == 0 && n % t == 0) { printf("最大公约数=%d\n", t); break; } else t--; } return 0; } ``` 此方法适用于简单的场景，但对于较大数值效率较低[^2]。 --- #### 方法二：辗转相除法 该方法基于欧几里得原理，不断用较大数除以较小数并取余数作为新的较大数，直至余数为零。此时的较小数即为最大公约数。 ```c #include<stdio.h> int gcd(int x, int y) { int z = x % y; while (z != 0) { x = y; y = z; z = x % y; } return y; } int main() { int a, b; printf("输入两个正整数:\n"); scanf("%d%d", &a, &b); if (a < b) { // 确保a始终大于等于b int temp = a; a = b; b = temp; } int result = gcd(a, b); printf("最大公约数为：%d\n", result); return 0; } ``` 上述代码展示了如何使用函数封装逻辑来提高可读性和重用性[^3]。 --- #### 方法三：更相减损术 这是一种古老的中国算法，其核心思想是通过对两个数做连续减法操作直到两者相等为止，最终得到的结果便是它们的最大公约数。 ```c #include<stdio.h> int gcd_subtraction(int x, int y) { int sum1 = 1; while ((x % 2 == 0) && (y % 2 == 0)) { sum1 *= 2; x /= 2; y /= 2; } while (1) { if (x < y) { int temp = x; x = y; y = temp; } int diff = x - y; if (diff == y) break; x = y; y = diff; } return y * sum1; } int main() { int a = 98, b = 63; int max_gcd = gcd_subtraction(a, b); printf("%d 和 %d 的最大公约数为 %d\n", a, b, max_gcd); return 0; } ``` 这段程序还考虑到了当初始两数均为偶数的情况下的优化处理[^3]。 --- #### 方法四：改进版辗转相除法（带参数传递） 为了进一步简化代码结构，可以采用递归形式表达辗转相除过程。 ```c #include<stdio.h> int gcd_recursive(int x, int y) { if (y == 0) return x; else return gcd_recursive(y, x % y); } int main() { int num1, num2; printf("请输入两个正整数: "); scanf("%d%d", &num1, &num2); int res = gcd_recursive(num1, num2); printf("最大公约数为:%d\n", res); return 0; } ``` 这种递归方式不仅简洁明了而且易于理解[^4]。 --- ### 总结 以上四种方法各有优劣，在实际应用中可根据具体需求选择合适的方式实现最大公约数计算功能。通常推荐使用 **辗转相除法** 或其变体，因其具有较高的执行效率和广泛的适用范围。