gcd求最大公约数

Greatest Common Divisor(GCD)

欧几里得算法据说是最早的算法，用于计算最大公约数，也是数论的基础算法之一。

这里给出使用欧几里得算法求最大公约数的递归和非递归的程序，同时给出穷举法求最大公约数的程序。

从计算时间上看，递推法计算速度最快。

/*
 * 计算两个数的最大公约数三种算法程序
 */
 
#include <stdio.h>
 
//#define DEBUG
#ifdef DEBUG
int c1=0, c2=0, c3=0;
#endif
 
int gcd1(int, int);
int gcd2(int, int);
int gcd3(int, int);
 
int main(void)
{
    int m=42, n=140;
 
    printf("gcd1: %d %d result=%d\n", m, n, gcd1(m, n));
    printf("gcd2: %d %d result=%d\n", m, n, gcd2(m, n));
    printf("gcd3: %d %d result=%d\n", m, n, gcd3(m, n));
#ifdef DEBUG
    printf("c1=%d  c2=%d  c3=%d\n", c1, c2, c3);
#endif
 
    return 0;
}
 
/* 递归法：欧几里得算法，计算最大公约数 */
int gcd1(int m, int n)
{
#ifdef DEBUG
    c1++;
#endif
    return (m==0)?n:gcd1(n%m, m);
}
 
/* 迭代法（递推法）：欧几里得算法，计算最大公约数 */
int gcd2(int m, int n)
{
    while(m>0)
    {
#ifdef DEBUG
    c2++;
#endif
        int c = n % m;
        n = m;
        m = c;
    }
    return n;
}
 
/* 连续整数试探算法，计算最大公约数 */
int gcd3(int m, int n)
{
    if(m>n) {
        int temp = m;
        m = n;
        n = temp;
    }
    int t = m;
    while(m%t || n%t)
    {
#ifdef DEBUG
    c3++;
#endif
        t--;
    }
    return t;
}

关键代码（正解）：

/* 迭代法（递推法）：欧几里得算法，计算最大公约数 */
int gcd(int m, int n)
{
    while(m>0)
    {
        int c = n % m;
        n = m;
        m = c;
    }
    return n;
}

作者：海岛Blog
来源：CSDN
原文：https://blog.csdn.net/tigerisland45/article/details/51151529
版权声明：本文为博主原创文章，转载请附上博文链接！