首页用辗转相除法求最大公约数c语言

用辗转相除法求最大公约数c语言

时间: 2024-11-28 18:18:32 浏览: 77

辗转相除法，也称为欧几里得算法，是一种古老的求解两个正整数最大公约数（Greatest Common Divisor，GCD）的有效方法。在C语言中，可以按照以下步骤实现： ```c #include <stdio.h> // 函数声明，返回两个整数的最大公约数 int gcd(int a, int b); // 主函数 int main() { int num1, num2; printf("请输入两个正整数："); scanf("%d %d", &num1, &num2); // 如果b为0，说明a就是最大公约数 if (num2 == 0) { printf("两数的最大公约数是：%d\n", num1); } else { // 否则，递归调用gcd函数 int result = gcd(num1, num2); printf("两数的最大公约数是：%d\n", result); } return 0; } // 辗转相除法计算GCD的函数 int gcd(int a, int b) { if (b == 0) return a; // 当b为零时结束递归，a即为结果 else return gcd(b, a % b); // 把较小的数赋给b，较大的数对较小数取余，然后继续这个过程 } ``` 在这个程序中，`gcd`函数通过不断将较大数替换为两数相除的余数，直到余数变为0，此时的非余数值即为最大公约数。

阅读全文