早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。

#include <stdlib.h>
#include <stdio.h>

//辗转相除法求最大公约数
int gcd(int m, int n)
{
	int r;
	r=m%n;
	if(r == 0)
		return n;
	else
		return gcd(n, r);
}

void main()
{
	int m,n;
	printf("请输入2个整数: ");
	scanf("%d,%d",&m,&n);
	printf("%d,%d的最大公约数为: %d \n", m, n, gcd(m, n));
	
	system("pause");
}

运行结果