跳到主要内容

C 编程：寻找两个数字的最大公约数

要理解这个例子，你需要了解以下 C 语言编程 主题的知识：

两个整数的最高公因数（HCF）或最大公约数（GCD）是能够完全整除这两个数的最大整数（没有余数）。

在 C 语言编程中，有许多方法可以找到最大公约数。

示例 #1：使用 for 循环和 if 语句计算 GCD​

#include <stdio.h>
int main()
{
    int n1, n2, i, gcd;

    printf("输入两个整数：");
    scanf("%d %d", &n1, &n2);

    for(i=1; i <= n1 && i <= n2; ++i)
    {
        // 检查 i 是否是两个整数的公因数
        if(n1 % i == 0 && n2 % i == 0)
            gcd = i;
    }

    printf("%d 和 %d 的最大公约数是 %d", n1, n2, gcd);

    return 0;
}

在这个程序中，用户输入的两个整数被存储在变量 n1 和 n2 中。然后，for 循环迭代，直到 i 小于等于 n1 和 n2。

在每次迭代中，如果 n1 和 n2 都能被 i 完全整除，i 的值就被赋给 gcd。

当 for 循环完成后，两个数的最大公约数被存储在变量 gcd 中。

示例 #2：使用 while 循环和 if...else 语句计算 GCD​

#include <stdio.h>
int main()
{
    int n1, n2;

    printf("输入两个正整数：");
    scanf("%d %d", &n1, &n2);

    while(n1 != n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    printf("最大公约数 = %d", n1);

    return 0;
}

输出

输入两个正整数：81
153
最大公约数 = 9

这是一种更好的查找 GCD 的方法。在这种方法中，较小的整数从较大的整数中减去，结果被赋值给保存较大整数的变量。这个过程一直持续到 n1 和 n2 相等。

上述两个程序只有在用户输入正整数时才能正常工作。这里对第二个示例进行了一点修改，以便同时找到正整数和负整数的 GCD。

示例 #3：对正数和负数计算 GCD​

#include <stdio.h>
int main()
{
    int n1, n2;

    printf("输入两个整数：");
    scanf("%d %d", &n1, &n2);

    // 如果用户输入负数，将数字的符号改为正数
    n1 = (n1 > 0) ? n1 : -n1;
    n2 = (n2 > 0) ? n2 : -n2;

    while(n1 != n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    printf("最大公约数 = %d", n1);

    return 0;
}

输出

输入两个整数：81
-153
最大公约数 = 9

你也可以使用 [

递归来查找 GCD](/tutorials/c-examples/hcf-recursion)。

最后于 更新