用辗转相除法求最大公约数
时间: 2024-06-14 16:03:24 浏览: 13
以下是使用辗转相除法求最大公约数的Python代码:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
```
其中,a和b为两个非负整数,函数返回它们的最大公约数。
举个例子,如果要求48和60的最大公约数,可以这样调用函数:
```python
print(gcd(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;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)