C 求两个数的 GCD 的程序-立地货

求两个数的 GCD 的 C 程序

使用循环和决策语句计算两个整数(正整数和负整数)的 GCD 的不同方法示例。

要理解此示例，您应该了解以下C 编程主题:

C 编程运算符

C for 循环

C if...else 语句

C while 和 do...while 循环

两个整数的 HCF 或 GCD 是可以整除两个数字的最大整数(没有余数)。

在 C 编程中找到最大公约数的方法有很多。

示例 #1: GCD 使用 for 循环和 if 语句

#include <stdio.h>
int main()
{
    int n1, n2, i, gcd;
    printf("Enter two integers: ");
    scanf("%d %d", &n1, &n2);
    for(i=1; i <= n1 && i <= n2; ++i)
    {
        // Checks if i is factor of both integers
        if(n1%i==0 && n2%i==0)
            gcd = i;
    }
    printf("G.C.D of %d and %d is %d", n1, n2, gcd);
    return 0;
}

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

在每次迭代中，如果 n1 和 n2 都可以被 i 整除，则 i 的值分配给 gcd。

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

示例 2: GCD 使用 while 循环和 if...else 语句

#include <stdio.h>
int main()
{
    int n1, n2;
    
    printf("Enter two positive integers: ");
    scanf("%d %d",&n1,&n2);
    while(n1!=n2)
    {
        if(n1 > n2)
            n1-= n2;
        else
            n2-= n1;
    }
    printf("GCD = %d",n1);
    return 0;
}

输出

Enter two positive integers: 81
153
GCD = 9

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

以上两个程序只有在用户输入正整数时才能按预期工作。下面是对第二个示例的一些修改，以找到正整数和负整数的 GCD。

示例 3: 正数和负数的 GCD

#include <stdio.h>
int main()
{
    int n1, n2;
    printf("Enter two integers: ");
    scanf("%d %d",&n1,&n2);
    // if user enters negative number, sign of the number is changed to positive
    n1 = ( n1 > 0) ? n1 :-n1;
    n2 = ( n2 > 0) ? n2 :-n2;
    while(n1!=n2)
    {
        if(n1 > n2)
            n1-= n2;
        else
            n2-= n1;
    }
    printf("GCD = %d",n1);
    return 0;
}

输出

Enter two integers: 81
-153
GCD = 9

您也可以使用递归查找GCD。