编写一个程序，求两个非负整数的最大公因子

以下是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;
}

已知 ，求 的值。 输入格式 第一行是一个整数 ，表示样例的个数。 以后每行一个样例，为三个整数 。 输出格式 依次每行输出一个样例的结果，如果结果为整数，那就输出整数；否则，输出a/b的分数形式，并保证分子与分母互素，且分母为非负整数。

这段描述看起来是在处理一个数学问题，具体来说是要求解两个分数的乘积。给定的输入是一组样例，每个样例包含三个整数 a, b 和 c。你需要计算的是 (a * b) / c 的值。如果这个结果是一个整数，直接输出该整数即可。如果不是整数，你需要将其转换成最简分数形式（即分子和分母互质），并确保分母是非负的。

为了完成这个任务，你可以编写一个程序，其中包含以下几个步骤：

1. 首先，计算乘法部分 `a * b`。
2. 然后，用得到的结果除以 `c`，取商和余数。
3. 如果余数为0，说明结果是整数，直接输出。
4. 否则，计算最大公约数（GCD）来找到分数的简化因子。可以使用欧几里得算法来找出 `a * b` 和 `c` 的最大公约数。
5. 最终结果就是分子 `a * b` 除以最大公约数，分母则是 `c`。

下面是简单的 C 语言代码实现：

#include <stdio.h>
#include <math.h>

// 计算最大公约数
int gcd(int num1, int num2) {
    if (num2 == 0)
        return num1;
    return gcd(num2, num1 % num2);
}

// 输出分数，确保分子和分母互质
void output_fraction(int numerator, int denominator) {
    if (gcd(numerator, denominator) == 1) {
        printf("%d/%d\n", numerator, denominator);
    } else {
        // 如果不是互质，输出简化后的分数
        int common_divisor = gcd(numerator, denominator);
        printf("%d/%d\n", numerator / common_divisor, denominator / common_divisor);
    }
}

int main() {
    int T; // 样本数量
    scanf("%d", &T);

    while (T--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        int product = a * b;
        int quotient = product / c;

        // 检查是否整除
        if (product % c == 0) {
            printf("%d\n", quotient);
        } else {
            output_fraction(product, c);
        }
    }

    return 0;
}