求最大公约数

时间:2021-02-01 00:35:53
算法1:
#include <iostream>
using namespace std;

int gcd(int M, int N)
{
	int R;
	R=M % N;
	if(M<=0 || N<=0)return 0;
	if(R == 0)return N;
	return gcd(N,R);
}

int main()
{
	int m,n,r;
	cout<<"Please input two numbers:";
	cin>>m>>n;
	r=gcd(m,n);
	cout<<r<<" is the greatest common divisor"<<endl;
	return 0;
}


算法2:(1)求m除n的余数r;

(2)若r=0,n为最大公约数;

(3)否则令m=n,n=r,回到第1步

int main()  
{  
	int m, n, r;
	printf("please input two numbers:");
	scanf("%d%d",&m,&n);
	while(1)
	{
		r = m % n;
		if (r == 0)
			break;
		else
		{
			m = n;
			n = r;
		}
	}
	printf("%d is the greatest common divisor!\n", n);
	return 0;  
}