欧几里得算法

可以使用辗转相除的方法求解两个数的最大公因子。

证明：
令c=gcd(a,b),a>=b,
令r=a mod b
设a=kc，b=jc，则k，j互素，否则c不是最大公约数
据上，r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍数，且k-mj与j互素(假设k-mj=xd，j=yd (d>1)，则k=mj+xd=myd+xd=(my+x)d，则a=kc=(my+x)cd，b=jc=ycd，则a与b的一个公约数cd>c，故c非a与b的最大公约数，与前面结论矛盾)，否则与前述k，j互素矛盾,
由此可知，b与r的最大公约数也是c，即gcd(a,b)=gcd(b,a mod b)，得证。

C++代码实现如下：

#include <iostream>
#include <algorithm>
using namespace std;

unsigned int gcd(unsigned int a, unsigned int b)
{
    if (b > a )
        swap(a, b);

    unsigned  int r = a % b;
    if (r == 0)
        return b;
    else
        return gcd(b, r);
}

int main(int argc, char ** argv)
{
    int a = 10;
    int b = 15;
    cout << "Input:" << a << ", " << b << endl;
    cout << "Output:" << gcd(a, b) << endl;
    return 0;
}