c语言辗转相除法 c语言辗转相除法求最大公约数

c语言辗转相除法的原理

c语言中辗转相除法的原理是，

辗转相除法是用来求最大公约数的一种方法。在许多计算机语言中都有。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 ?? 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。剩下的还没有变成零的数就是两数的最大公约数。

3个数怎么用辗转相除法

回答如下：辗转相除法是求两个数的最大公约数的方法，对于三个数，可以先求出其中两个数的最大公约数，再用这个最大公约数和第三个数求最大公约数。具体步骤如下：

1.用辗转相除法求出第一个数a和第二个数b的最大公约数gcd(a,b)。

2.用gcd(a,b)和第三个数c求最大公约数，即gcd(gcd(a,b),c)。

3.得到三个数的最大公约数gcd(a,b,c)。

注：如果第一步求得的最大公约数为1，则三个数互质，最大公约数为1。

什么叫做辗转相除法？举几个例子

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

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

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

解：

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

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

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

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

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

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

所以（15750，27216）=216

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

c语言怎么输出一个最简分数

要输出一个最简分数，需要先通过辗转相除法或欧几里得算法求出分子和分母的最大公约数，然后将分子和分母分别除以最大公约数得到约分后的分数。在C语言中，可以使用辗转相除法或欧几里得算法来求最大公约数，然后使用printf()函数输出约分后的分数。具体的代码实现需要根据具体情况进行调整，需要注意避免分母为零的情况。