辗转相除法求最大公约数c++代码（辗转相除法）

大家好，我是小新，我来为大家解答以上问题。辗转相除法求最大公约数c++代码，辗转相除法很多人还不知道，现在让我们一起来看看吧！

1、辗转相除法最大的用途就是用来求两个数的最大公约数。

2、用（a,b）来表示a和b的最大公约数。有定理：已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。（证明过程请参考其它资料）

3、例：求 15750 与27216的最大公约数。

4、解：

5、∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466）

6、∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284)

7、∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898）

8、∵4284=2898×1+1386 ∴（4284，2898）=（2898，1386）

9、∵2898=1386×2+126 ∴（2898，1386）=（1386，126）

10、∵1386=126×11 ∴（1386，126）=126

11、所以（15750，27216）=216

12、辗转相除法比较适合用来求两个比较大的数的最大公约数。

13、扩展资料；

14、辗转相除法，又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

15、另一种求两数的最大公约数的方法是更相减损法。

16、两个数的最大公约数是指能同时整除它们的最大正整数。

17、设两数为a、b(a≥b)，求a和b最大公约数

18、的步骤如下：

19、(1)用a除以b(a≥b)，得

20、。

21、(2)若

22、，则

23、；

24、(3)若

25、，则再用b除以

26、，得