最大公约数GCD的三种算法程序

Greatest Common Divisor(GCD)

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

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

从计算时间上看&＃xff0c;递推法计算速度最快。

程序中包含条件编译语句用于统计分析计算复杂度。

/** 计算两个数的最大公约数三种算法程序*/#include //#define DEBUG
#ifdef DEBUG
int c1&＃61;0, c2&＃61;0, c3&＃61;0;
#endifint gcd1(int, int);
int gcd2(int, int);
int gcd3(int, int);int main(void)
{int m&＃61;42, n&＃61;140;printf("gcd1: %d %d result&＃61;%d\n", m, n, gcd1(m, n));printf("gcd2: %d %d result&＃61;%d\n", m, n, gcd2(m, n));printf("gcd3: %d %d result&＃61;%d\n", m, n, gcd3(m, n));
#ifdef DEBUGprintf("c1&＃61;%d c2&＃61;%d c3&＃61;%d\n", c1, c2, c3);
#endifreturn 0;
}/* 递归法&＃xff1a;欧几里得算法&＃xff0c;计算最大公约数 */
int gcd1(int m, int n)
{
#ifdef DEBUGc1&＃43;&＃43;;
#endifreturn (m&＃61;&＃61;0)?n:gcd1(n%m, m);
}/* 迭代法&＃xff08;递推法&＃xff09;&＃xff1a;欧几里得算法&＃xff0c;计算最大公约数 */
int gcd2(int m, int n)
{while(m>0){
#ifdef DEBUGc2&＃43;&＃43;;
#endifint c &＃61; n % m;n &＃61; m;m &＃61; c;}return n;
}/* 连续整数试探算法&＃xff0c;计算最大公约数 */
int gcd3(int m, int n)
{if(m>n) {int temp &＃61; m;m &＃61; n;n &＃61; temp;}int t &＃61; m;while(m%t || n%t){
#ifdef DEBUGc3&＃43;&＃43;;
#endift--;}return t;
}

关键代码&＃xff08;正解&＃xff09;&＃xff1a;

/* 迭代法&＃xff08;递推法&＃xff09;&＃xff1a;欧几里得算法&＃xff0c;计算最大公约数 */
int gcd(int m, int n)
{while(m>0){int c &＃61; n % m;n &＃61; m;m &＃61; c;}return n;
}