The greatest common divisor gcd（最大公约数）

文章某些部分有借鉴大神处，共勉之。

说到最大公约数的算法，最熟悉的还是辗转相除法，又名欧几里德算法（Euclidean algorithm）。在求最大公数的时候，辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：

1. 若 r 是 a ÷ b 的余数， 则gcd(a,b) = gcd(b,r)

2. a 和其倍数之最大公因子为 a。

另一种写法是：

1. a ÷ b，令r为所得余数（0≤r＜b），若 r = 0，算法结束；b 即为答案。

2. 互换：置 a←b，b←r，并返回第一步。

第一种写法是利用递归实现，第二种可以更清楚的看出其辗转过程。实现代码如下：

int gcd(int m,int n)   //递归 
{
    if(n==0)   
      return  m;
    else 
      return  gcd(n,m%n);
}
//调用：  n=gcd(a,b);
           

int gcd(int m,int n)   //递归 
{
    if(n==0)   
      return  m;
    else 
      return  gcd(n,m%n);
}
//调用：  n=gcd(a,b);
           

今天第一次了解另一种求最大公约数算法——更相减损法（等值算法），其实个人认为也可理解为辗转相减法。。。

此处借用百科解释一下其原理：《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下： 

第一步：任意给定两个正整数，判断它们是否都是偶数。若是，用2约简；若不是执行第二步；

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。循环执行这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。

代码如下：

int gcd(int m,int n)   //更相减损法 
{
    while(m!=n)     //辗转相减
    {
      if(m>n)
        m-=n;
       else
         n-=m; 
    } 
    return m;
} 
           

实现代码如下，由于本人属于小水一名，简单的东西容易忘记，代码中附加了几种变量交换方式 ，共勉之。

#include <stdio.h>
#include <iostream>
using namespace std;

int gcd(int m,int n)   //递归 
{
    if(n==0)   
      return  m;
    else 
      return  gcd(n,m%n);
}

/*
int gcd(int m,int n)   //辗转相除法 
{
    int p;
    while(n)
    {
      p=m%n;
      m=n;
      n=p;
    }
    return m;
}

int gcd(int m,int n)   //更相减损法 
{
    while(m!=n)
    {
      if(m>n)
        m-=n;
       else
         n-=m; 
    } 
    return m;
} 
 */

void swap(int &m,int &n)   //引用 ，交换变量 (无返回值)
{
     int temp;
     temp=m;
     m=n;
     n=temp;     
 } 

/*void swap(int *m,int *n)  //指针，交换变量 
{
     int temp;
     temp=*m;
     *m=*n;
     *n=temp;
 } 
 调用：swap(&m,&n); 
 
 int swap(int &m,int &n)    //不用辅助变量，交换 (此两种方法指针通用)
 {
     m=m+n;
     n=m-n;
     m=m-n; 
 } 
 调用：swap(m,n);
  
 int swap(int &m,int &n)
 {
     m=m^n;
     n=n^m;
     m=m^n;
 } 
 调用：swap(m,n);
 */
 
int main()
{
     int a,b;
     
     while(1)
     { 
     printf("please enter the two positive integers: ");
     scanf("%d%d",&a,&b);
     if(a<b)
       swap(a,b); 
     printf("the greatest common divisor gcd: %d\n\n",gcd(a,b));
     }
     
     system("pause");
     return 0; 
}