最大公约数问题的两种方法

最大公因数，又称最大公约数。是指 [n(≧2)个自然数 a1, a2, ..., an] 的最大公因数。通常有两种表示方式：

• 它们的所有公因数中最大的那一个；
• 如果自然数 m 是这 n 个自然数的公因数，且这 n 个数的任意公因数都是 m 的因数，就称 m 是这 n 个数的最大用因数。通常国内的记述方式为 [(a1, a2, ..., an)] ，国际通用的记号为 [g.c.d.(a1, a2, ..., an)]。

欧几里得算法(Euclidean Algorithm)(Euclid‘s 算法)就是通常所说的求最大公因数的辗转相除法。算法描述如下：

1. 如果 a 除以 b 能整除，则最大公约数是 b；
2. 否则，最大公约数等于 b 和 a % b的公约数。

代码实现如下：

#include 
int Euclidean(int parA, int parB)
{
    if (parB == 0) {
        return parA;
    } else {
        return Euclidean(parB, parA % parB);
    }
}
int main(void)
{
    int intA, intB;
    printf("Enter two number to calculate its GCD:\n");
    scanf("%d %d", &intA, &intB);
    printf("The GCD of %d and %d is %d\n", intA, intB, Euclidean(intA, intB));
    return 0;
}

或者

#include 
int Euclidean(int parA, int parB)
{
    return (!parB)?parA : Euclidean(parB, parA % parB);
}
int main(void)
{
    int intA, intB;
    printf("Enter two number to calculate its GCD:\n");
    scanf("%d %d", &intA, &intB);
    printf("The GCD of %d and %d is %d\n", intA, intB, Euclidean(intA, intB));
    return 0;
}

本文地址：http://www.nowamagic.net/librarys/veda/detail/451，欢迎访问原出处。