C语言编程实现辗转相除法求余数
时间: 2024-09-13 17:00:53 浏览: 46
齐齐哈尔大学C语言题程序设计(部分).pdf
在C语言中,辗转相除法也叫欧几里得算法,用于计算两个整数的最大公约数(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 {
int result = gcd(num1, num2); // 调用gcd函数
printf("两数的最大公约数为:%d\n", result);
}
return 0;
}
// 辗转相除法实现
int gcd(int a, int b) {
if (b == 0) {
return a; // 当b为0时,a即为最大公约数
} else {
return gcd(b, a % b); // 递归地调用自身,直到b为0
}
}
```
在这个程序中,`gcd()`函数通过不断将较大的数替换为两数相除后的余数,直到余数为0,此时较小的数就是两数的最大公约数。
阅读全文