下载文档原格式
求最大公约数的两种算法最大公约数（GCD）是指能够同时整除两个或多个整数的最大正整数。
在数学和计算机科学中，求最大公约数是一个常见的问题，并有多种算法可以解决。
以下是两种常见的求最大公约数的算法：1.暴力法：暴力法，也称为穷举法或试除法，是最简单直观的求最大公约数的方法。
该方法使用一个循环来遍历从2到较小的那个数之间所有的可能公约数，然后找到最大的。
算法步骤：-输入两个整数a和b，其中a>=b。
-从2开始，从小到大的顺序依次遍历所有的整数，直到找到最大的公约数。
-对于每一个遍历到的整数i，判断它是否同时整除a和b，如果是则更新最大公约数。
-返回最大公约数。
该算法的时间复杂度取决于较小整数b的大小，即O(b)。
然而，该算法对于较大的整数效率比较低，而且无法处理负整数。
2.辗转相除法（欧几里得算法）：辗转相除法是一种通过反复用较小数除较大数，然后用余数去除旧的较小数，直到余数为0的方式来求解最大公约数的算法。
该算法基于下面的原理：两个整数a和b的最大公约数等于b和a mod b的最大公约数。
算法步骤：-输入两个整数a和b，其中a>=b。
- 计算a mod b，使用较小数b去除较大数a，将余数保存下来。
-如果余数为0，则b即为最大公约数。
-如果余数不为0，则将b赋值给a，将余数赋值给b，回到第二步继续计算。
-返回b作为最大公约数。
辗转相除法的时间复杂度较低，约为O(log b)。
它比暴力法更加高效且适用于处理较大整数。
此外，该算法也能正确处理负整数。
这两种算法是求最大公约数最常用的方法，它们在数学和计算机科学的许多领域都有广泛的应用。
可以根据具体情况选择合适的算法来求解最大公约数。
C语⾔实现求最⼤公约数的三种⽅法⽬录题⽬描述问题分析代码实现⽅法⼀：穷举法⽅法⼆：辗转相除法⽅法三：更相减损法题⽬描述求任意两个正整数的最⼤公约数问题分析最⼤公因数，也称最⼤公约数、最⼤公因⼦，指两个或多个整数共有约数中最⼤的⼀个。
a，b的最⼤公约数记为（a，b），同样的，a，b，c的最⼤公约数记为（a，b，c），多个整数的最⼤公约数也有同样的记号。
求最⼤公约数有多种⽅法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。
与最⼤公约数相对应的概念是最⼩公倍数，a，b的最⼩公倍数记为[a，b]。
——百度百科最⼤公因数的求法有不少，本⽂我将采⽤穷举法、辗转相除法、更相减损法三种⽅法，求两个正整数的最⼤公约数（最⼤公因数）。
代码实现⽅法⼀：穷举法穷举法（列举法），是最简单最直观的⼀种⽅法。
具体步骤为：先求出两个数的最⼩值min（最⼤公约数⼀定⼩于等于两个数的最⼩值），接着从最⼩值min递减遍历（循环结束条件为i > 0），如果遇到⼀个数同时为这两个整数的因数，则使⽤break退出遍历（退出循环），这时的遍历值i即为两个正整数的最⼤公约数。
#include <stdio.h>/*** @brief 获取两个正整数的最⼤公因数（穷举法）* @param num1 第⼀个正整数* @param num2 第⼆个正整数* @return 最⼤公因数*/int Get_Max_Comm_Divisor(int num1, int num2){int i = 0;//获取两个整数的最⼩值int min = num1 < num2 ? num1 : num2;//从两个数的最⼩值开始递减遍历for(i = min; i > 0; i--){//i为num1和num2的公倍数if(num1 % i == 0 && num2 % i == 0)break;}return i;}int main(){int num1 = 0, num2 = 0;puts("请输⼊两个正整数.");scanf("%d%d", &num1, &num2);printf("最⼤公约数为%d.\n", Get_Max_Comm_Divisor(num1, num2));运⾏结果⽅法⼆：辗转相除法辗转相除法⼜称欧⼏⾥得算法，是指⽤于计算两个⾮负整数a，b的最⼤公约数。
求两个整数m,n的最大公约数的欧几里德算法
欧几里德算法，也称辗转相除法，是一种求两个数的最大公约数的算法。
方法如下：设a和b是两个不全为0的整数，求它们的最大公约数。
不妨设a > b，用a除以b，得到余数r，将b除以r，得到余数r1，将r除以r1，得到余数r2，如此继续进行，每次将所得的商作为除数，余数作为被除数，直到余数为0为止，此时所得的被除数即为a和b的最大公约数。
可以通过递归来实现欧几里德算法。
例如，假设有两个整数m和n，我们可以使用如下Python代码来实现欧几里德算法：
def gcd(m, n):
if n == 0:
return m
else:
return gcd(n, m % n)
在这个函数中，如果n等于0，则返回m，否则通过递归调用gcd(n, m % n)来继续求解。
这个算法的正确性可以通过数学归纳法来证明。
首先，当n等于0时，gcd(m, n)等于m，显然成立。
接下来，假设gcd(n, m % n)等于d，则gcd(m, n)等于gcd(n, m % n)等于d，也就是说，d是m和n的公因数。
另一方面，如果x是m和n的公因数，则它也是n和m % n的公因数。
因此，d是m和n的最大公因数。
欧几里德算法的时间复杂度为O(log(max(m, n)))，因为每一次递归都能将一个参数减半。
因此，这个算法在实践中是非常高效的。
总之，欧几里德算法是求两个数的最大公约数的一种简单而优美的方法，递归实现更容易理解和实现，且在时间复杂度上表现出色，因此在实际应用中被广泛使用。
数的最大公约数求两个数的最大公约数的方法假设我们需要求两个数的最大公约数（Greatest Common Divisor，简称GCD），有多种方法可以实现。
一、辗转相除法辗转相除法是求两个数最大公约数的一种常见方法。
具体步骤如下：1. 计算两个数的余数，将较大数除以较小数，取余数。
2. 将较小数替换为原来的较大数，将余数替换为原来的较小数。
3. 重复步骤1和步骤2，直到余数为0。
4. 最后一个余数不为0的数即为最大公约数。
举例说明：求78和66的最大公约数。
1. 78除以66，余数为12。
2. 将66替换为78，将12替换为66。
3. 66除以12，余数为6。
4. 将12替换为66，将6替换为12。
5. 12除以6，余数为0。
因此，最大公约数为6。
二、更相减损术更相减损术是另一种求两个数最大公约数的方法。
具体步骤如下：1. 比较两个数的大小，将较大数减去较小数。
2. 将较小数替换为原来的较大数，将差值替换为原来的较小数。
3. 重复步骤1和步骤2，直到两个数相等。
4. 相等的数即为最大公约数。
举例说明：求68和46的最大公约数。
1. 68减去46，差值为22。
2. 将46替换为68，将22替换为46。
3. 46减去22，差值为24。
4. 将22替换为46，将24替换为22。
5. 22减去24，差值为-2。
6. 将24替换为22，将-2替换为24。
7. 24减去-2，差值为26。
8. 将-2替换为24，将26替换为-2。
9. -2减去26，差值为-28。
10. 将26替换为-2，将-28替换为26。
11. -2减去-28，差值为26。
12. 将-28替换为26，将26替换为-28。
因此，最大公约数为26。
三、辗转相减法与辗转相除法的比较辗转相减法的思路与辗转相除法类似，只是每次相减得到的差值较大，但是最终得到的最大公约数是相同的。
四、欧几里得算法（Euclidean Algorithm）欧几里得算法是一种高效的求最大公约数的方法，通常用于大数求解。
C语言求最大公约数和最小公倍数可以说是C语言编程学习中一个重点和难点，它常常作为计算机专业学生参加各种考试必须要把握的内容。
其算法方面除常用的辗转相除法外、还可以根据数学定义法、递归调用法等。
前提：假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。
1、辗转相除法辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理：a b=0gcd(a,b) =gcd(b,a mod b) b!=0根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下：①、函数嵌套调用其算法过程为：前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数1、大数放a中、小数放b中；2、求a/b的余数；3、若temp=0则b为最大公约数；4、如果temp!=0则把b的值给a、temp的值给a；5、返回第第二步；代码：int divisor (int a,int b) /*自定义函数求两数的最大公约数*/{int temp; /*定义整型变量*/if(a<b) /*通过比较求出两个数中的最大值和最小值*/{ temp=a;a=b;b=temp;} /*设置中间变量进行两数交换*/while(b!=0) /*通过循环求两数的余数，直到余数为0*/{temp=a%b;a=b; /*变量数值交换*/b=temp;}return (a); /*返回最大公约数到调用函数处*/}int multiple (int a,int b) /*自定义函数求两数的最小公倍数*/{int divisor (int a,int b); /*自定义函数返回值类型*/int temp;temp=divisor(a,b); /*再次调用自定义函数，求出最大公约数*/return (a*b/temp); /*返回最小公倍数到主调函数处进行输出*/}#include "stdio.h" /*输入输出类头文件*/main(){int m,n,t1,t2; /*定义整型变量*/printf("please input two integer number:"); /*提示输入两个整数*/scanf("%d%d",&m,&n); /*通过终端输入两个数*/t1=divisor(m,n); /*自定义主调函数*/t2=multiple(m,n); /*自定义主调函数*/printf("The higest common divisor is %d\n",t1);/*输出最大公约数*/printf("The lowest common multiple is %d\n", t2); /*输出最小公倍数*/}启示：请注意算法中变量数值之间的相互交换方法、如何取模、怎样进行自定义函数及主调函数与被调函数间的相互关系，函数参数的定义及对应关系特点，利用控制语句如何实现。
C语言实现欧几里得算法和扩展欧几里得算法欧几里得算法（Euclidean Algorithm）是一种用于求解两个整数的最大公约数的算法。
它是古希腊数学家欧几里得提出的，在数学上被广泛应用。
算法的基本思想是，通过多次用较小数去除较大数，直到两个数相等为止。
此时，两个数相等的值即为它们的最大公约数。
这是因为，如果一个数能整除另一个数，那么这两个数的公约数也能整除另一个数。
下面我们通过C语言实现欧几里得算法：```c#include <stdio.h>int euclidean_algorithm(int a, int b)while (b != 0)int temp = a;a=b;b = temp % b;}return a;int maiint a, b;printf("请输入两个整数：");scanf("%d%d", &a, &b);int gcd = euclidean_algorithm(a, b);printf("最大公约数为：%d\n", gcd);return 0;```在上面的代码中，`euclidean_algorithm` 函数使用while循环，将较大数除以较小数，然后将较小数赋值给较大数，较小数赋值为较大数取模较小数的结果。
当较小数为0时，循环终止，较大数即为最大公约数。
`main`函数通过`scanf`函数获取用户输入的两个整数，然后调用`euclidean_algorithm`函数得到最大公约数。
扩展欧几里得算法（Extended Euclidean Algorithm）是在欧几里得算法的基础上扩展而来的，它不仅能求解两个整数的最大公约数，还能求解两个整数的贝祖等式的一组解。
两个整数a和b的贝祖等式表示为：ax + by = gcd(a, b)，其中x 和y为整数。
扩展欧几里得算法的基本思想是通过递归计算，并利用欧几里得算法的性质。
《C 语言输出最大公约数和最小公倍数》在 C 语言编程中，计算最大公约数和最小公倍数是非常常见的需求之一。
它们是数学中的基本概念，对于计算机科学以及实际问题中都具有重要的意义。
本文将深入探讨如何在 C 语言中输出最大公约数和最小公倍数，并结合实际问题进行分析和应用。
## 1. 最大公约数让我们明确最大公约数的定义。
最大公约数，英文为 Greatest Common Divisor，通常缩写为 GCD，是两个整数的共同约数中最大的一个。
在 C 语言中，我们可以使用欧几里得算法来高效地计算两个数的最大公约数。
欧几里得算法的基本思想是通过不断取余的方式，直到余数为 0，那么除数就是最大公约数。
以下是 C 语言中计算最大公约数的代码示例：```cint gcd(int a, int b) {if (b == 0) {return a;} else {return gcd(b, a % b);}}```在上述代码中，我们定义了一个名为 `gcd` 的函数，它接收两个整数参数 `a` 和 `b`，然后通过递归调用自身来计算最大公约数。
这种递归的实现思路非常巧妙，而且在实际的程序中也能够高效地运行。
## 2. 最小公倍数接下来，让我们来讨论最小公倍数。
最小公倍数，英文为 Least Common Multiple，通常缩写为 LCM，是两个整数的共同倍数中最小的一个。
在C 语言中，我们可以通过最大公约数来计算最小公倍数，因为有一个基本的性质：两个整数的最大公约数与它们的最小公倍数的乘积等于这两个整数的乘积。
以下是 C 语言中计算最小公倍数的代码示例：```cint lcm(int a, int b) {return a / gcd(a, b) * b;}```在上述代码中，我们定义了一个名为 `lcm` 的函数，用来计算两个整数的最小公倍数。
通过调用之前我们定义的 `gcd` 函数，可以非常方便地实现对最小公倍数的计算。
编程求最大公约数的方法
有多种方法可以求两个数的最大公约数。
1. 辗转相除法：也称为欧几里得算法。
设两个数为a和b，先用a除以b得到余数c，再用b除以c得到余数d，再用c除以d得到余数e...重复这个过程直到余数为0，此时的除数就是a和b的最大公约数。
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
```
2. 更相减损法：设两个数为a和b，若a > b，则用a减去b得到差c，c和b的最大公约数即为a和b的最大公约数。
```python
def gcd(a, b):
while a != b:
if a > b:
a -= b
else:
b -= a
return a
```
3. 整除法：设两个数为a和b，先找到a和b的最小值min，然后从min开始递减，找到能同时整除a和b的最大数即为a和b的最大公约数。
```python
def gcd(a, b):
min_num = min(a, b)
for i in range(min_num, 0, -1):
if a % i == 0 and b % i == 0:
return i
return 1
```
其中，辗转相除法是最常用的方法，效率较高。
使用欧几里得算法计算两个正整数的最大公约数c语言使用欧几里得算法计算两个正整数的最大公约数是计算机领域中的经典问题之一，尤其在c语言中，这一算法广泛应用。
本文将探讨欧几里得算法的原理和实现方法，并深入介绍在c语言中如何编写代码来实现这一计算过程。
一、欧几里得算法原理欧几里得算法，又称辗转相除法，是一种用于计算两个正整数的最大公约数的算法。
其原理非常简单，即通过反复用较大数除以较小数，然后用除数去除余数，直至余数为0时，除数即为这两个正整数的最大公约数。
二、欧几里得算法实现在c语言中，可以通过递归或迭代的方式来实现欧几里得算法。
下面分别介绍这两种实现方法。
1. 递归实现递归是一种简洁而优雅的解决问题的方式，对于欧几里得算法也同样适用。
以下是c语言中使用递归实现欧几里得算法的代码示例：```cint gcd(int a, int b) {if (b == 0) {return a;} else {return gcd(b, a % b);}}```在这段代码中，函数gcd接受两个正整数参数a和b，返回它们的最大公约数。
当b等于0时，即找到了最大公约数，返回a的值；否则，递归调用gcd函数，传入参数为b和a除以b的余数。
2. 迭代实现除了递归，欧几里得算法还可以通过迭代的方式进行实现。
以下是c语言中使用迭代实现欧几里得算法的代码示例：```cint gcd(int a, int b) {while (b != 0) {int temp = a % b;a = b;b = temp;}return a;}```在这段代码中，使用while循环来不断更新a和b的值，直至b等于0，最终a的值就是这两个正整数的最大公约数。
三、个人观点欧几里得算法作为计算最大公约数的经典算法，不仅在c语言中得到了广泛的应用，也为其他编程语言提供了宝贵的思路。
其简洁、高效的特点使之成为解决相关问题的首选算法之一。
在实际开发中，对欧几里得算法的理解和掌握能够帮助我们更好地应对相关计算问题，提高代码的执行效率和性能。
欧⼏⾥得算法求最⼤公约数（GCD）的数学原理很早就学过欧⼏⾥得算法，但是⼀直不知道它的原理。
⼏乎每本算法书都会提到它，但是貌似只有数学书上才会见到它的原理。
前段时间粗粗看了点数论（《什么是数学》），惊讶于这个原理的奇妙。
现在把它通俗地写下来，以免⾃⼰忘记。
欧⼏⾥得算法是求两个数的最⼤公约数(Greatest Common Divisor (GCD))的算法，我们⾸先假设有两个数a和b，其中a是不⼩于b的数，记a被b除的余数为r，那么a可以写成这样的形式：a=bq+r其中q是整数（我们不需要去管q到底是多少，这和我们的⽬标⽆关）。
现在假设a和b的⼀个约数为u，那么a和b都能被u整除，即a=sub=tus和t都是整数（同样的，我们只需要知道存在这样的整数s和t就⾏）。
这样可以得出r=a−bq=su−(tu)q=(s−tq)u所以r也能被u整除，⼀般规律如下a和b的约数也整除它们的余数r，所以a和b的任⼀约数同时也是b和r的约数。
—— 条件⼀反过来可以得出b和r的任⼀约数同时也是a和b的约数。
——条件⼆这是因为对b和r每⼀个约数v，有b=kvr=cv于是有a=bq+r=(kv)q+cv=(kq+c)v由条件⼀和条件⼆可知a和b的约数的集合，全等于b和r的约数的集合。
于是a和b的最⼤公约数，就是b和r的最⼤公约数。
接下来⽤递推法，a÷b余r，现在设b÷r余r1r÷r1余r2……r n−3÷r n−2余r n−1r n−2÷r n−1余r n=0因为a≥b，可以看出余数r n会越来越⼩，最终变成 0.当r n−1≠0 且r n=0 时，可知r n−2可被r n−1整除（余数为 0 嘛）此时r n−2和r n−1的约数就只有：r n−1和r n−1的因数，所以他们的最⼤公约数就是r n−1！所以r n−1就是a和b的最⼤公约数。
（若r=0，则b为最⼤公约数）这个递推法写成c语⾔函数是这样的（⽐推导更简洁...）:unsigned int Gcd(unsigned int M,unsigned int N){unsigned int Rem;while(N){Rem = M % N;M = N;N = Rem;}return Rem;}可以发现这⾥没有要求M>=N，这是因为如果那样，循环会⾃动交换它们的值。
