前言
本篇文章总结了四种求最大公约数的常用算法。
包括:辗转相除法、穷举法(枚举法)、更相减损法、Stein算法。
每个算法都附加流程图及 C/C++ 代码,并对其时间复杂度进行了分析。
一、辗转相除法
1. 算法简介
辗转相除法又称欧几里得算法,是指用于计算两个正整数a,b的最大公约数。欧几里得算法可用于RSA加密等领域。
假如:需要求 2022 和 409 两个正整数的最大公约数,用欧几里得算法,是这样进行的:
2022 / 409 = 4 (余 386)
409 / 386 = 1(余 23)
386 / 23 = 16(余 18)
23 / 18 = 1 (余 5)
18 / 5 = 3 (余 3)
5 / 3 = 1 (余 2)
3 / 2 = 1 (余 1)
2 / 1 = 2 (余 0)
因此,最大公约数为1。
以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 2022 和 409 的最大公约数 1。
2. 算法描述
假设有两个数a、b (a > b),c为a与b的余数,求a与b的最大公约数。
使用步骤:
Step 1 将两个数分别存入a、b中,并满足 a > b
Step 2 求 c = a % b
Step 3 判断 c 是否为 0
Step 4 若 c == 0 则 b 为最大公约数;若 c != 0 则重复步骤 2 ~ 4
流程图:
3. 代码及复杂度
// 辗转相除法
int gcd(int a,int b)
{
if(a % b == 0)
return b;
else
return gcd(b ,a % b);
}
注意:调用该函数时,一定要保证 a > b
时间复杂度:O(log2n)
二、穷举法(枚举法)
1. 算法简介
将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,合适就保留,不合适就丢弃。
枚举算法要列举问题的所有可能的答案,所以它具备以下几个特点:
1、得到的结果肯定是正确的;
2、可能做了很多的无用功,浪费了宝贵的时间,效率低下。
3、通常会涉及到求极值(如最大,最小,最重等)。
4、数据量大的话,可能会造成时间崩溃。
2. 算法描述
采用枚举算法解题的基本思路:
(1)确定枚举对象、枚举范围和判定条件;
(2)枚举可能的解,验证是否是问题的解。
对于本算法,要从两个数中较小的数开始由大到小列举,找到公约数后立即中断列举,得到的公约数便是最大公约数。
流程图:
3. 代码及复杂度
// 穷举法(枚举法)
int divisor(int a, int b) // 求两数的最大公约数的函数 返回值为最大公约数
{
int temp;// 定义整型变量temp 临时储存需要判断是否为最大公约数的值
temp = (a > b) ? b : a;// 求出两个数中的最小值 赋给temp
while (temp > 0)
{
if (a % temp == 0 && b % temp == 0)// 只要找到一个数能同时被a,b所整除,则中止循环
break;
temp--;// 如不满足if条件则变量自减,直到能被a,b所整除
}
return (temp);
}
时间复杂度:O(n)
三、更相减损法
1. 算法简介
更相减损法又叫更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。
2. 算法描述
使用步骤:
Step 1 任意给定两个正整数;判断它们是否都是偶数。
Step 2 若是,则用2约简;若不是则执行Step 3。
Step 3 以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
Step 4 Step 2 中约掉的若干个 2 的积 与 Step 3 中等数的乘积 就是所求的最大公约数。
注:其中所说的 “等数” ,就是公约数。求 “等数” 的办法是 “更相减损法” 。
流程图:
3. 代码及复杂度
// 更相减损法
int gcd2(int a, int b)
{
int i = 0, temp, x;
while (a % 2 == 0 && b % 2 == 0)// 判断m和n能被多少个2整除
{
a /= 2;
b /= 2;
i++;
}
if (a < b) // a保存大的值
{
temp = a;
a = b;
b = temp;
}
do
{
x = a - b;
a = (b > x) ? b : x; // 更新大数的值
b = (b < x) ? b : x; // 更新小数的值
if (b == (a - b))
break;
}while (x);
if (i == 0)
return b;
else
return (int)pow(2, i) * b;
}
时间复杂度:O(n)
四、Stein算法(二进制算法)
1. 算法简介
Stein算法是一种计算两个数最大公约数的算法,是针对欧几里德算法在对大整数进行运算时,需要试商导致增加运算时间的缺陷而提出的改进算法。
Stein算法与欧几里德算法的对比:
欧几里德算法每次迭代中最恶劣的情况是,a = 2b - 1,这样,迭代后,r=b-1。
如果a小于2n,这样大约需要4n次迭代。
而Stein算法,每次迭代后,显然An+1Bn+1≤ AnBn/2,最大迭代次数也不超过4n次。
也就是说,迭代次数几乎是相等的。但是,需要注意的是,对于大素数,试商法将使每次迭代都更复杂,因此对于大素数,Stein算法将更有优势。
2. 算法描述
原理:gcd(kx,ky)=k*gcd(x,y)
对两个正整数 x>y ,分为以下情况:
均为偶数 gcd(x,y)=2gcd(x/2,y/2);
均为奇数 gcd(x,y)=gcd((x+y)/2,(x-y)/2);
x奇 y偶 gcd(x,y)=gcd(x,y/2);
x偶 y奇 gcd(x,y)=gcd(x/2,y) 或 gcd(x,y)=gcd(y,x/2).
流程图:文章来源:https://www.toymoban.com/news/detail-436957.html
3. 代码及复杂度
//Stein算法
int Stein(unsigned int x, unsigned int y) // 求 x 和 y 的最大公因数
{
int factor = 0;
int temp;
if (x < y) // 使两个数 x > y
{
temp = x;
x = y;
y = temp;
}
if (y == 0) // 排除求0的最大公因数的情况
{
return 0;
}
while (x != y)
{
if (x & 0x1) // x为奇数
{
if (y & 0x1) // x为奇数 y也为奇数
{
y = (x - y) >> 1;
x -= y;
}
else // x为奇数 y为偶数
{
y >>= 1;
}
}
else // x为偶数
{
if (y & 0x1) // x为偶数 y为奇数
{
x >>= 1;
if (x < y)
{
temp = x;
x = y;
y = temp;
}
}
else // x为偶数 y也为偶数
{
x >>= 1;
y >>= 1;
++factor;
}
}
}
return (x << factor);
}
时间复杂度:O(log2n)文章来源地址https://www.toymoban.com/news/detail-436957.html
到了这里,关于四种求最大公约数的算法 C / C++的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!