编辑计算两个正整数的最大公约数
时间: 2023-11-25 20:28:54 浏览: 43
算法1:辗转相除法
1. 对于给定的两个正整数a和b,令r为a除以b的余数,若r为0,则b即为两数的最大公约数;否则令a=b,b=r,再计算a除以b的余数,重复上述步骤,直到余数为0为止。
实现如下:
int gcd(int a, int b)
{
int r;
while (b > 0)
{
r = a % b;
a = b;
b = r;
}
return a;
}
算法2:辗转相减法
1. 对于给定的两个正整数a和b,若a>b,则令a=a-b;若a<b,则令b=b-a,重复上述步骤,直到a=b为止。
实现如下:
int gcd(int a, int b)
{
while (a != b)
{
if (a > b)
a = a - b;
else
b = b - a;
}
return a;
}
算法3:更相减损法
1. 对于给定的两个正整数a和b,若a>b,则令a=a-b;若a<b,则令b=b-a;若a=b,则a或b即为所求的最大公约数;重复上述步骤,直到a和b的差值小于等于其中的一个数。
实现如下:
int gcd(int a, int b)
{
while (a != b)
{
if (a > b)
a = a - b;
else
b = b - a;
if (a < b)
swap(a, b);
}
return a;
}
以上三种算法都是比较常用的求最大公约数的方法,其中辗转相除法是最常用的一种方法,因为它的迭代次数最少,效率最高。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)