`Greatest Common Divisor` (最大公约数) GCD(m, n) is: if m modulo n equals 0 then n; else GCD(n, m mod n);

代码

#include<iostream>
#include<cstdlib>

using namespace std;

int gcd(int a, int b)
{

	// swap a and b
	if (a<b)
	{
		a = a^b; b = a^b; a = a^b;
	}

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


int main()
{
	srand(6);
	int a, b;
	for (int i=0; i<10; ++i)
	{
		a = rand(), b= rand();
		cout << " The greastest common divisor of " << a 
			<< " and " << b << " is " << gcd(a, b) 
			<< endl;
	}

}

原理

求最大公约数算法：

**辗转相除法**

有两整数a和b:

1. a%b得余数c
2. 若c=0，则b即为两数的最大公约数
3. 若c≠0，则a=b，b=c，再回去执行①

例如求27和15的最大公约数过程为：

1. 27÷15 余12 
2. 15÷12余3
3. 12÷3余0

因此，3即为最大公约数