用辗转相除法求最小公约数
时间: 2023-05-21 10:02:40 浏览: 115
辗转相除法是一种求最大公约数和最小公倍数的方法,我们可以通过不断地用较小的数去除较大的数,直到余数为0,此时较小的数就是最大公约数,最小公倍数可以通过两数之积除以最大公约数得到。以下是用辗转相除法求最小公约数的步骤:
1. 用较大的数除以较小的数,得到余数r和商q。
2. 如果r为0,则较小的数即为最小公约数。
3. 如果r不为0,则用较小的数除以r,得到余数r1和商q1。
4. 如果r1为0,则r即为最小公约数。
5. 如果r1不为0,则继续用r除以r1,得到余数r2和商q2,直到余数为0为止。
例如,求48和60的最小公约数:
60 ÷ 48 = 1 … 12
48 ÷ 12 = 4 … 0
因此,48和60的最小公约数为12。
相关问题
利用C语言用辗转相除法求最大公约数
以下是利用C语言用辗转相除法求最大公约数的代码:
```c
#include <stdio.h>
int main() {
int a, b, t;
scanf("%d %d", &a, &b);
while (b != 0) {
t = a % b;
a = b;
b = t;
}
printf("%d", a);
return 0;
}
```
这段代码中,我们输入两个数a和b,然后利用while循环进行辗转相除,直到b为0时,此时a的值就是最大公约数。这种方法比较高效,时间复杂度为O(logn)。
--相关问题--:
1. 什么是最大公约数和最小公倍数?
2. C语言中如何进行输入
用辗转相除法求最大公约数 c语言
以下是用辗转相除法求最大公约数的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
int main() {
int a, b, r;
printf("请输入两个数:\n");
scanf("%d %d", &a, &b);
while (b != 0) {
r = a % b;
a = b;
b = r;
}
printf("最大公约数:%d\n", a);
system("pause");
return 0;
}
```