euclid.cpp

初学密码内容

//欧几里德算法：求两数最大公约数
#include <iostream.h>
#include <conio.h>

//算法说明：辗转相除法
//输入：两正整数a,b
//输出：函数返回a与b的最大公因式

int gcd(int a, int b)		//函数gcd()即为求a, b两数最大公约数的过程 
{							//返回值为a与b最大公约数
	int A=a;				//A为辗转相除法中的被除数
	int B=b;				//B为辗转相除法中的除数
	int R;					//R为A与B相除所得的余数
	while (B>0)
	{
		R = A % B;
		A = B;  B=R;
	}
	return A;
}

void main()					//测试程序（求m与n的最大公因式）
{
	int m ;
	int n ;
	cout<<"***正在运行求两数最大公因式程序***"<<endl;
	cout<<endl<<"请输入一个数m的值: ";
	cin>>m;
	cout<<endl<<"请输入另一个数n的值: ";
	cin>>n;

	cout<<endl<<"m与n的最大公因式为: "<<gcd(m, n)<<endl;
	cout<<endl<<"Press any key to Quit "<<endl;
	getch();
}