c语言最大公约数算法
时间: 2023-11-18 12:56:55 浏览: 48
C语言最大公约数算法有多种实现方式,以下是其中两种常见的方法:
方法一:辗转相除法
辗转相除法,也叫欧几里得算法,是求最大公约数的一种常用方法。其基本思想是用较大数除以较小数,再用除数除以出现的余数(第一次除的余数是较小数),不断重复这个过程,直到余数为0为止,此时除数就是最大公约数。
代码实现:
```
int gcd(int a, int b) {
int temp;
while (b != 0) {
temp = a % b;
a = b;
b = temp;
}
return a;
}
```
方法二:更相减损术
更相减损术是古老的一种求最大公约数的方法,其基本思想是用两个数中的较大数减去较小数,然后用得到的差值和较小数继续做减法,直到两个数相等为止,此时的数就是最大公约数。
代码实现:
```
int gcd(int a, int b) {
if (a == b) {
return a;
}
if (a < b) {
return gcd(b, a);
}
return gcd(a - b, b);
}
```
相关问题
最大公约数算法 c语言
以下是三种C语言中求最大公约数的算法:
1. 辗转相除法(欧几里德法):
```c
int divisor(int a, int b) {
int temp;
if (a < b) {
temp = a;
a = b;
b = temp;
}
while (b != 0) {
temp = a % b;
a = b;
b = temp;
}
return a;
}
```
2. 函数递归调用:
```c
int gcd(int a, int b) {
if (a % b == 0)
return b;
else
return gcd(b, a % b);
}
```
3. 穷举法:
```c
int gcd(int a, int b) {
int i, gcd;
for (i = 1; i <= a && i <= b; i++) {
if (a % i == 0 && b % i == 0)
gcd = i;
}
return gcd;
}
```
C语言欧几里得算法求最大公约数
C语言欧几里得算法是一种高效地求解两个整数最大公约数的方法。该算法的基本原理是:两个整数a和b(a>b)的最大公约数等于b和a mod b的最大公约数。通过重复应用这个原理,我们可以递归地求解最大公约数,直到b为0为止。在C语言中,我们可以使用递归函数来实现欧几里得算法,代码非常简洁易懂。下面是一个示例代码:
```
#include <stdio.h>
// 求最大公约数的欧几里得算法
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
int num1, num2;
printf("请输入两个整数:");
scanf("%d %d", &num1, &num2);
int result = gcd(num1, num2);
printf("最大公约数是:%d\n", result);
return 0;
}
```
在上述代码中,我们定义了一个名为gcd的函数,该函数接受两个整数a和b作为参数,并返回它们的最大公约数。函数内部首先检查b是否为0,如果是,那么a就是最大公约数,我们直接返回a。否则,我们递归地调用gcd函数,将b和a mod b作为新的参数传递给它。在main函数中,我们首先从用户输入中读取两个整数num1和num2,然后调用gcd函数计算它们的最大公约数,并将结果存储在result变量中。最后,我们使用printf函数将最大公约数输出到屏幕上。