c语言辗转相除法求最大公约数for循环
时间: 2024-01-06 22:23:57 浏览: 41
以下是使用C语言编写的辗转相除法求最大公约数的for循环实现:
```c
#include <stdio.h>
int main() {
int a, b, t, gcd;
scanf("%d %d", &a, &b);
for (int i = 1; i <= a && i <= b; i++) {
if (a % i == 0 && b % i == 0) {
gcd = i;
}
}
printf("%d", gcd);
return 0;
}
```
该程序首先从用户输入中读取两个整数a和b,然后使用for循环从1到a和b中较小的那个数进行遍历,如果a和b都能被当前的数整除,则将当前的数作为最大公约数gcd。最后输出gcd即可。
相关问题
C语言辗转相除法求最大公约数
辗转相除法(又称欧几里得算法)是求两个正整数的最大公约数的一种方法。该算法基于如下原理:两个数的最大公约数等于其中较小的数和两数相除余数的最大公约数。
以下是使用 C 语言实现辗转相除法的代码:
```c
#include <stdio.h>
int gcd(int a, int b) {
int temp;
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int a, b, result;
printf("请输入两个正整数:\n");
scanf("%d %d", &a, &b);
result = gcd(a, b);
printf("%d和%d的最大公约数是%d\n", a, b, result);
return 0;
}
```
在该代码中,`gcd()` 函数接收两个参数 `a` 和 `b`,并返回它们的最大公约数。在 `main()` 函数中,用户输入两个正整数,然后调用 `gcd()` 函数来计算它们的最大公约数,并将结果输出到屏幕上。
这段代码的核心是 while 循环。在每次循环中,我们计算 `a` 除以 `b` 的余数,并将结果赋值给 `a`。然后,将原来的 `b` 的值赋给 `a`,将余数赋给 `b`。这个过程一直持续到 `b` 变成 0,此时 `a` 的值就是两数的最大公约数。
c语言用辗转相除法求最大公约数
以下是使用辗转相除法在C语言中求最大公约数的代码和解释:
```c
#include <stdio.h>
int gcd(int a, int b) {
int c = a % b;
while (c) {
a = b;
b = c c = a % b;
}
return b;
}
int main() {
int m, n;
scanf("%d%d", &m, &n);
int ret = gcd(m, n);
printf("%d\n", ret);
return 0;
}
```
代码解释:
1. 首先定义了一个名为`gcd`的函数,该函数接受两个整数参数`a`和`b`,返回它们的最大公约数。
2. 在函数中,定义了一个变量`c`,用于存储`a`除以`b`的余数。
3. 使用`while`循环,当`c`不为0时,执行以下操作:
a. 将`b`的值赋给`a`,将`c`的值赋给`b`,更新被除数和除数。
b. 计算新的`c`的值,即`a`除以`b`的余数。
4. 当`c`为0时,`b`的值即为`a`和`b`的最大公约数,将其返回。
5. 在`main`函数中,首先读入两个整数`m`和`n`。
6. 调用`gcd`函数,将`m`和`n`作为参数传入,得到它们的最大公约数。
7. 将最大公约数打印输出。