1.穷举法

如果大数可以整除小数，那么最大公约数为小数。如果不能整除小数，那么这两个数就按大到小依次对比小数小的数求余，遇到都能够整除的，就是最大公约数。

<code>int gcd(int a, int b)

{

int i;

int min = a < b ? a : b;

for (i = min; i >= 1; i--)

{

if (a % i == 0 && b % i == 0)

break;

}

return i;

}

2.辗转相除法

用a对b求余，若余数为0，则除数b为最大公约数。若余数不为0，将此余数r作为新的除数，b作为新的被除数，重新求余，直到余数为0为止。此时的最大公约数为除数。

a.常规辗转

int gcd(int a, int b)

{

int t;

while(a % b)//当a%b为0时，跳出循环，最大公约数为b

{

r = a % b;

a = b;

b = t;

}

return b;

}

b.递归辗转

int gcd(int a, int b)

{

int r = a % b;

if (0 == r)

return b;//当余数为0时，b就为最大公约数

else

return gcd(b, r);

}

3.更相减损法

当两个数相等时，最大公约数为他们其中任意一个；当两个数不相等时，用大数减小数得到的差和之前的那个小数再次相减，直到两个数相等，相等的两个中，任意一个都是最大公约数。

a.常规

int gcd(int a, int b)

{

if (a > b) a = a - b;

if (a < b) b = b - a;

if (a == b) return a;

}

b.递归

int gcd(int a, int b)

{

if (a == b) return a;//当a=b时，返回

if (a < b)

{

return gcd(a, b - a);

}

return gcd(a - b, b);

}

4.质因数分解法

int gcd(int a, int b)

{

int result = 1, i;

for (i = 2; i <= a && i <= b; i++)

{

while (a % i == 0 && b % i == 0)

{

result *= i;

a /= i;

b /= i;

}

}

return result;

}