博客

辗转相除法又名广义欧几里得除法，是用来求解两个数的最大公约数的最佳算法之一。

算法原理：若a除以b的余数为r , 则有 (a , b) = ( b ,r )  （(a,b)表示a和b的最大公约数）

例：169与48的最大公约数求解过程

169 = 48 * 3 + 25


—— (169 , 48) = (48 , 25)

48 = 25 * 1 + 13


——(48 , 25) = (25 , 13)

25 = 13 * 1 + 12

13 = 12 * 1 + 1

12 = 1 * 12  + 0


——(12 , 1 ) = 1

故最大公约数为 1

下面是C++实现的算法，使用的递归算法

#include <iostream>
#include <conio.h>
using namespace std;

int gcd(int a, int b){
	return b == 0 ? a : gcd(b, a % b);
}

int main()
{
	cout << gcd(169, 48) << endl;
	_getch();
	return 0;
}