`
阿尔萨斯
  • 浏览: 4107884 次
社区版块
存档分类
最新评论

算法 - 求两个自然数的最大公约数(C++)

 
阅读更多

//****************************************************************************************************
//
//  求两个自然数的最大公约数 - C++ - by Chimomo
//
//  辗转相除法
//
//****************************************************************************************************

#include <iostream>
#include <cassert>
#include <stack>
#include <math.h>

using namespace std ;

int GreatestCommonDivisor(int a, int b)
{
	int temp;

	if(a < b)
	{
		// 交换两个数,使大数放在a的位置上。
		temp = a;
		a = b;
		b = temp;
	}

	while(b != 0)
	{
		// 利用辗转相除法,直到b为0为止。
		temp = a % b;
		a = b;
		b = temp;
	}

	return a;
}

int main()
{
	cout << GreatestCommonDivisor(318, 87632) << endl;
	return 0;
}

// Output:
/*
2
*/
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics