(1)辗转相除法（欧几里得算法）
辗转相除法基本思想：两正整数的最大公约数等于较大的数对较小的数取模的结果与较小的数的最大公约数，即：
$$gcd(a,b)=gcd(b, a\%b), a\geq{b}$$
#include
using namespace std;
// greatest common divisor
// 仅用于计算两正整数的最大公约数
// 辗转相除法: gcd(a,b)=gcd(b, a%b), a>=b
int gcd(int a, int b)
{
if (a<b) // 交换a，b的值，保证a>=b
{
a = a^b;
b = a^b;
a = a^b;
}
if (b!=0)
return gcd(b, a%b);
else
return a;
}
int main(int argc, char *argv[])
{
cout << gcd(33, 77) << endl;
return 0;
}
(2) Stein算法
前面的辗转相除法在处理较小的数时具有相当高的效率，但当处理大数时取模运算需用试商法计算，这大大增加了算法的时间复杂度。Stein算很好的解决了辗转相除法的缺陷。
算法思想：
1) 如果a==0，返回b；
2) 如果b==0，返回a；
3) 如果a、b均为偶数，返回2*gcd(a/2, b/2)；
4) 如果a为偶数，b为奇数，返回gcd(a/2, b)；
5) 如果a为奇数，b为偶数，返回gcd(a, b/2);
6) 如果a、b均为奇数，返回gcd((a-b)/2, b)（a>=b时，可在算法开始出比较a、b，保证a>=b）。
#include
using namespace std;
// greatest common divisor
// 仅用于计算两正整数的最大公约数
// Stein算法：使用位移和减法代替除法和取模运算，以解决辗转相除法处理的缺点。
int gcd(int a, int b)
{
if (a<b) // 交换a，b的值，保证a>=b
{
a = a^b;
b = a^b;
a = a^b;
}
// if (a==0)
// return b;
if (b==0)
return a;
if ((a&0x1)==0 && (b&0x1)==0) // a，b均为偶数
return 2*gcd(a>>1, b>>1);
if ((a&0x1)==0 && (b&0x1)!=0) // a为偶数，b为奇数
return gcd(a>>1, b);
if ((a&0x1)!=0 && (b&0x1)==0) // a为奇数，b为偶数
return gcd(a, b>>1);
if ((a&0x1)!=0 && (b&0x1)!=0) // a，b均为奇数
return gcd((a-b)>>1, b);
}
int main(int argc, char *argv[])
{
cout << gcd(33, 77) << endl;
return 0;
}