输入两个整数,求两个数的最大公约数
时间: 2024-01-05 07:49:48 浏览: 33
可以使用辗转相除法,也称欧几里得算法,来求解两个整数的最大公约数。
假设要求解的两个整数为a和b(a>b),则有:
1. 用a除以b,得到余数r。
2. 若r=0,则b即为最大公约数。
3. 若r≠0,则用b除以r,得到余数r1。
4. 若r1=0,则r即为最大公约数。
5. 若r1≠0,则重复步骤3和4,直到余数为0,最后的除数即为最大公约数。
以下为Python代码实现:
```
def gcd(a, b):
while b != 0:
r = a % b
a = b
b = r
return a
```
调用该函数,输入两个整数a和b,即可得到它们的最大公约数:
```
a = int(input("请输入第一个整数:"))
b = int(input("请输入第二个整数:"))
print("最大公约数为:", gcd(a, b))
```
相关问题
输入两个整数求其最大公约数和最小公倍数
以下是Python实现输入两个整数求其最大公约数和最小公倍数的代码:
```python
# 定义函数,求最大公约数
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 定义函数,求最小公倍数
def lcm(a, b):
return a * b // gcd(a, b)
# 输入两个整数
num1 = int(input("请输入第一个整数:"))
num2 = int(input("请输入第二个整数:"))
# 输出最大公约数和最小公倍数
print("{0}和{1}的最大公约数为:{2}".format(num1, num2, gcd(num1, num2)))
print("{0}和{1}的最小公倍数为:{2}".format(num1, num2, lcm(num1, num2)))
```
运行结果:
```
请输入第一个整数:24
请输入第二个整数:36
24和36的最大公约数为:12
24和36的最小公倍数为:72
```
C语言输入两个整数求最大公约数
好的,以下是 C 语言的代码实现:
```
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
int a, b;
printf("请输入两个整数:");
scanf("%d %d", &a, &b);
int result = gcd(a, b);
printf("它们的最大公约数为:%d", result);
return 0;
}
```
其中,gcd 函数为求最大公约数的函数,main 函数中通过 scanf 获取用户输入的两个整数,然后调用 gcd 函数求它们的最大公约数,并输出结果。这样,您就可以使用 C 语言来解决您的问题了。