C++计算最大公约数（辗转相除法）

你是否正在寻找关于辗转相除法的内容？让我把最直接的东西奉献给你：

典型例题：

一.辗转相除法

例1 。求两个正数8251和6105的最大公因数。

（分析：辗转相除→余数为零→得到结果）

解：8251＝6105×1＋2146

显然8251与6105的最大公因数也必是2146的因数，同样6105与2146的公因数也必是8251的因数，所以8251与6105的最大公因数也是6105与2146的最大公因数。

6105＝2146×2＋1813

2146＝1813×1＋333

1813＝333×5＋148

333＝148×2＋37

148＝37×4＋0

则37为8251与6105的最大公因数，。

以上我们求最大公因数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。

1． 为什么用这个算法能得到两个数的最大公因数？

利用辗转相除法求最大公因数的步骤如下：

第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；

第二步：若r0＝0，则n为m，n的最大公因数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；

第三步：若r1＝0，则r1为m，n的最大公因数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；

……

依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公因数。

练习：利用辗转相除法求两数4081与20723的最大公因数。

2。辗转相除法包含重复操作的步骤，因此我们可用__循环_______结构来构造算法，

利用辗转相除法求最大公因数的步骤：

以上就是关于辗转相除法的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-1869-1.html