编写一个程序,求两个非负整数的最大公因子
时间: 2023-05-26 09:04:59 浏览: 57
以下是Python代码实现:
```python
def gcd(a, b):
if a == 0:
return b
return gcd(b % a, a)
a = int(input("请输入非负整数a: "))
b = int(input("请输入非负整数b: "))
result = gcd(a, b)
print("最大公因子是: ", result)
```
这个程序中,我们定义了一个递归函数 `gcd(a, b)`,其中 `a` 和 `b` 分别是两个非负整数。程序的执行如下:
1. 如果 `a` 等于 0,那么显然 `b` 是它们的最大公因子,直接返回 `b` 即可。
2. 如果 `a` 不等于 0,那么我们求 `b` 对 `a` 取模的结果 `b % a`,并递归调用 `gcd(b % a, a)` 直到 `a` 等于 0。
注意到在第二步中,我们将 `b % a` 作为第一个参数传给了 `gcd` 函数,而将 `a` 作为第二个参数传给了 `gcd` 函数。这是因为我们希望 `a` 始终表示模数,而 `b` 始终表示被模数。在递归调用中,我们希望每次将模数作为第二个参数传入,这样才能保证 `a` 始终表示模数。
最后,我们读取用户输入的两个非负整数 `a` 和 `b`,计算它们的最大公因子并输出结果。
相关问题
编写一个程序,求两个非负整数的最大公因子c语言
#include <stdio.h>
int main()
{
int num1, num2, i, gcd;
printf("Enter two non-negative integers: ");
scanf("%d %d", &num1, &num2);
for (i = 1; i <= num1 && i <= num2; i++)
{
if (num1 % i == 0 && num2 % i == 0)
{
gcd = i;
}
}
printf("GCD of %d and %d is: %d\n", num1, num2, gcd);
return 0;
}
求两个非负整数的最大公约数函数
好的,这是一个求两个非负整数的最大公约数函数的示例代码:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
这个函数使用了辗转相除法来求两个数的最大公约数。如果你有其他问题,请随时问我。