gcd.c

来自「《数据结构-使用C语言》第三版」· C语言 代码 · 共 45 行

//最大公约数
#include<stdio.h>
int Gcd(int n,int m)
{
	if(n<0||m<0)exit(0);
	
	if(m==0)return n;
	else if(m>n)return Gcd(m,n);
	else return Gcd(m,n%m);
}

int Gcd2(int n, int m)
{
	int tn, tm, temp;
	if(n<0||m<0)exit(0);
	
	if(m<n)
	{
		tn=m;
		tm=n;
	}
	else 
	{
		tn=n;
		tm=m;
	}
	while(tm!=0)
	{
		temp=tn;
		tn=tm;
		tm=temp%tm;
	}
	return tn;
}

int main()
{
	int n, m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		printf("%d %d\n",Gcd(n,m),Gcd2(n,m));
	}
	return 0;
}