简明现代魔法 -> 计算机算法 -> 求解最大公约数问题

求解最大公约数问题

2010-08-13

最大公因数,又称最大公约数。是指 [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 <stdio.h>

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 <stdio.h>

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;
}
随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们