C语言求两个非负整数的最大公约数,
时间: 2024-09-10 18:24:07 浏览: 20
在C语言中,求两个非负整数的最大公约数(Greatest Common Divisor, GCD)通常使用辗转相除法(也称欧几里得算法)。这种方法基于一个定理:两个正整数a和b(a > b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。算法的基本步骤如下:
1. 比较两个数,将较大的数作为a,较小的数作为b。
2. 计算a除以b的余数c。
3. 如果c为0,则b即为两数的最大公约数。
4. 如果c不为0,则将b的值赋给a,将c的值赋给b。
5. 重复步骤2到4,直到找到最大公约数为止。
以下是一个C语言实现最大公约数的函数示例:
```c
#include <stdio.h>
// 函数声明
int gcd(int a, int b);
int main() {
int num1, num2, result;
printf("请输入两个非负整数:");
scanf("%d %d", &num1, &num2);
result = gcd(num1, num2); // 调用求最大公约数的函数
printf("最大公约数是:%d\n", result);
return 0;
}
// 函数定义:使用辗转相除法求两个非负整数的最大公约数
int gcd(int a, int b) {
int c;
while (b != 0) { // 当b不为0时循环
c = a % b; // 计算余数
a = b; // 将b的值赋给a
b = c; // 将余数c赋给b
}
return a; // 当b为0时,a即为最大公约数
}
```