求最大公约数-多种算法-高效

小白弟弟

最大公约数，也称最大公因数、最大公因子是指两个或多个整数共有约数中最大的一个。
我将用多种方法计算出两个数的最大公约数
思路/代码/源码回复可见



最简单的是枚举法：
对两个整数a和b，共同的约数在1到min(a,b)[也就是求a和b哪个小]之间，从大到小枚举，若判断它能同时整除a和b两个数，即为两个数的最大公约数
代码：
这个_MIN的函数要保留！！，因为方法2也用到该函数！！

  

子程序名	返回值类型	公开	备 注
_MIN	整数型
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

如果真 (a ＜ b)
返回 (a)
返回 (b)

.版本 2<br /> <br /> .子程序 _MIN, 整数型<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> <br /> .如果真 (a ＜ b)<br />     返回 (a)<br /> .如果真结束<br /> 返回 (b)

  

子程序名	返回值类型	公开	备 注
gcd1	整数型		枚举
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

变量名	类 型	静态	数组	备 注
i	整数型

变量循环首 (_MIN (a, b), 0, -1, i)
如果真 (a ％ i ＝ 0 且 b ％ i ＝ 0)
返回 (i)

变量循环尾 ()
返回 (1)

.版本 2<br /> <br /> .子程序 gcd1, 整数型, , 枚举<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> .局部变量 i, 整数型<br /> <br /> .变量循环首 (_MIN (a, b), 0, -1, i)<br />     .如果真 (a ％ i ＝ 0 且 b ％ i ＝ 0)<br />         返回 (i)<br />     .如果真结束<br /> <br /> .变量循环尾 ()<br /> <br /> 返回 (1)

解释：a%i表示a除i的余数，a%i=0就是a能被i整除，即a是i的倍数或i是a的倍数。
这个算法的最坏时间复杂度为O(min(a,b))




从数学上讲使用方法1的分解质因数的方法，可以令我们从另一方面加深对公约数的理解。例如：a=24，b=60时，对a和b分解质因数得到：
a=2*2*2*3
b=2*2*3*5
收集共有的质因数是2、2、3，得到的最大公约数为：2*2*3=12
代码：

  

子程序名	返回值类型	公开	备 注
gcd2	整数型		短除法变形
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

变量名	类 型	静态	数组	备 注
gcd	整数型
i	整数型

gcd ＝ 1
i ＝ 2
判断循环首 (i × i ≤ _MIN (a, b))
判断循环首 (a ％ i ＝ 0 且 b ％ i ＝ 0)  ' 收集公共质因数
a ＝ a ÷ i
b ＝ b ÷ i
gcd ＝ gcd × i
判断循环尾 ()
判断循环首 (a ％ i ＝ 0)  ' a去掉a有b没有的质因数
a ＝ a ÷ i
判断循环尾 ()
判断循环首 (b ％ i ＝ 0)  ' b去掉a有b没有的质因数
b ＝ b ÷ i
判断循环尾 ()
i ＝ i ＋ 1
判断循环尾 ()
如果 (a ％ b ＝ 0)  ' 剩余的a和b必须有一个是质数或1
gcd ＝ gcd × b
如果 (b ％ a ＝ 0)
gcd ＝ gcd × a




返回 (gcd)

.版本 2<br /> <br /> .子程序 gcd2, 整数型, , 短除法变形<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> .局部变量 gcd, 整数型<br /> .局部变量 i, 整数型<br /> <br /> gcd ＝ 1<br /> i ＝ 2<br /> .判断循环首 (i × i ≤ _MIN (a, b))<br />     .判断循环首 (a ％ i ＝ 0 且 b ％ i ＝ 0)  ' 收集公共质因数<br />         a ＝ a ÷ i<br />         b ＝ b ÷ i<br />         gcd ＝ gcd × i<br />     .判断循环尾 ()<br />     .判断循环首 (a ％ i ＝ 0)  ' a去掉a有b没有的质因数<br />         a ＝ a ÷ i<br />     .判断循环尾 ()<br />     .判断循环首 (b ％ i ＝ 0)  ' b去掉a有b没有的质因数<br />         b ＝ b ÷ i<br />     .判断循环尾 ()<br /> <br />     i ＝ i ＋ 1<br /> .判断循环尾 ()<br /> <br /> .如果 (a ％ b ＝ 0)  ' 剩余的a和b必须有一个是质数或1<br />     gcd ＝ gcd × b<br /> .否则<br />     .如果 (b ％ a ＝ 0)<br />         gcd ＝ gcd × a<br />     .否则<br /> <br />     .如果结束<br /> <br /> .如果结束<br /> <br /> 返回 (gcd)

解释：由于有i*i<=min（a,b）的优化，时间复杂度降为O(sqrt(min(a,b)))。循环完后，a和b有一个可能没分解完，要注意收集到gcd中，这个算法也可以看成是短除法的变形




我们在方法1采用了低效的算法——枚举法。下面让我们尝试用数学知识找到一种更好的算法！
假设c是a和b的最大公约数（假设a>b)，那么有a%c=0，且，b%c=0，则（a-b)%c=0亦成立，即若c是b和a-b的公约数，c亦是a和b的公约数。两个公约数集合相等，两个集合中的
最大数也必然相等，简单讲就是：gcd（a，b）=gcd（b，a-b）。
因此我们可以采用函数进迭送，当迭到a=b时，a为a和b的最大公约数，即答案
用《九章算术》中的“更相减损法”求正整数a和b的最大公约数，即答案
代码：

  

子程序名	返回值类型	公开	备 注
gcd3	整数型		更相减损法
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

如果真 (a ＝ b)
返回 (a)
如果真 (a ＜ b)  ' 保证a>=b
交换变量 (a, b)
返回 (gcd3 (b, a － b))

.版本 2<br /> <br /> .子程序 gcd3, 整数型, , 更相减损法<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> <br /> .如果真 (a ＝ b)<br />     返回 (a)<br /> .如果真结束<br /> .如果真 (a ＜ b)  ' 保证a>=b<br />     交换变量 (a, b)<br /> .如果真结束<br /> 返回 (gcd3 (b, a － b))

这个算法很简洁！但可惜的是效率依然可能较低，比如说a很大，b很小时。那么我们是否可以再加以优化呢？
可以用方法3类似的方法证明：gcd(a,b)=gcd(b,a%b)(a>b)。
这样的话，我们就可以设计出一个更为高效的算法——欧几里德算法。
代码：

  

子程序名	返回值类型	公开	备 注
gcd4	整数型		欧几里德算法
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

如果真 (b ＝ 0)
返回 (a)
返回 (gcd4 (b, a ％ b))

.版本 2<br /> <br /> .子程序 gcd4, 整数型, , 欧几里德算法<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> <br /> .如果真 (b ＝ 0)<br />     返回 (a)<br /> .如果真结束<br /> 返回 (gcd4 (b, a ％ b))

欧几里德算法的时间复杂度是多少呢？a>b时
（1）若b<=a/2，gcd(a,b)变为gcd(b,a%b)，显然规模至少缩小一半。
（2）若b>a/2，a%b也最少缩小为a的一半。
总之进过一次迭代，gcd(a,b)的数据规模至少会变成原来的一半，所以这个算法的时间复杂度是O(lonN)。
全部代码：

  

窗口程序集名	保 留	保 留	备 注
程序集1

子程序名	返回值类型	公开	备 注
_启动子程序	整数型		本子程序在程序启动后最先执行

调试输出 (gcd1 (145396, 65200))
调试输出 (gcd2 (145396, 65200))
调试输出 (gcd3 (145396, 65200))
调试输出 (gcd4 (145396, 65200))
返回 (0)  ' 可以根据您的需要返回任意数值

子程序名	返回值类型	公开	备 注
gcd1	整数型		枚举
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

变量名	类 型	静态	数组	备 注
i	整数型

变量循环首 (_MIN (a, b), 0, -1, i)
如果真 (a ％ i ＝ 0 且 b ％ i ＝ 0)
返回 (i)

变量循环尾 ()
返回 (1)

子程序名	返回值类型	公开	备 注
gcd2	整数型		短除法变形
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

变量名	类 型	静态	数组	备 注
gcd	整数型
i	整数型

gcd ＝ 1
i ＝ 2
判断循环首 (i × i ≤ _MIN (a, b))
判断循环首 (a ％ i ＝ 0 且 b ％ i ＝ 0)  ' 收集公共质因数
a ＝ a ÷ i
b ＝ b ÷ i
gcd ＝ gcd × i
判断循环尾 ()
判断循环首 (a ％ i ＝ 0)  ' a去掉a有b没有的质因数
a ＝ a ÷ i
判断循环尾 ()
判断循环首 (b ％ i ＝ 0)  ' b去掉a有b没有的质因数
b ＝ b ÷ i
判断循环尾 ()
i ＝ i ＋ 1
判断循环尾 ()
如果 (a ％ b ＝ 0)  ' 剩余的a和b必须有一个是质数或1
gcd ＝ gcd × b
如果 (b ％ a ＝ 0)
gcd ＝ gcd × a




返回 (gcd)

子程序名	返回值类型	公开	备 注
gcd3	整数型		更相减损法
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

如果真 (a ＝ b)
返回 (a)
如果真 (a ＜ b)  ' 保证a>=b
交换变量 (a, b)
返回 (gcd3 (b, a － b))

子程序名	返回值类型	公开	备 注
gcd4	整数型		欧几里德算法
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

如果真 (b ＝ 0)
返回 (a)
返回 (gcd4 (b, a ％ b))

子程序名	返回值类型	公开	备 注
_MIN	整数型
参数名	类 型	参考	可空	数组	备 注
a	整数型
b	整数型

如果真 (a ＜ b)
返回 (a)
返回 (b)

i支持库列表	支持库注释
spec	特殊功能支持库

.版本 2<br /> .支持库 spec<br /> <br /> .程序集 程序集1<br /> <br /> .子程序 _启动子程序, 整数型, , 本子程序在程序启动后最先执行<br /> <br /> 调试输出 (gcd1 (145396, 65200))<br /> 调试输出 (gcd2 (145396, 65200))<br /> 调试输出 (gcd3 (145396, 65200))<br /> 调试输出 (gcd4 (145396, 65200))<br /> <br /> 返回 (0)  ' 可以根据您的需要返回任意数值<br /> <br /> .子程序 gcd1, 整数型, , 枚举<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> .局部变量 i, 整数型<br /> <br /> .变量循环首 (_MIN (a, b), 0, -1, i)<br />     .如果真 (a ％ i ＝ 0 且 b ％ i ＝ 0)<br />         返回 (i)<br />     .如果真结束<br /> <br /> .变量循环尾 ()<br /> <br /> 返回 (1)<br /> <br /> .子程序 gcd2, 整数型, , 短除法变形<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> .局部变量 gcd, 整数型<br /> .局部变量 i, 整数型<br /> <br /> gcd ＝ 1<br /> i ＝ 2<br /> .判断循环首 (i × i ≤ _MIN (a, b))<br />     .判断循环首 (a ％ i ＝ 0 且 b ％ i ＝ 0)  ' 收集公共质因数<br />         a ＝ a ÷ i<br />         b ＝ b ÷ i<br />         gcd ＝ gcd × i<br />     .判断循环尾 ()<br />     .判断循环首 (a ％ i ＝ 0)  ' a去掉a有b没有的质因数<br />         a ＝ a ÷ i<br />     .判断循环尾 ()<br />     .判断循环首 (b ％ i ＝ 0)  ' b去掉a有b没有的质因数<br />         b ＝ b ÷ i<br />     .判断循环尾 ()<br /> <br />     i ＝ i ＋ 1<br /> .判断循环尾 ()<br /> <br /> .如果 (a ％ b ＝ 0)  ' 剩余的a和b必须有一个是质数或1<br />     gcd ＝ gcd × b<br /> .否则<br />     .如果 (b ％ a ＝ 0)<br />         gcd ＝ gcd × a<br />     .否则<br /> <br />     .如果结束<br /> <br /> .如果结束<br /> <br /> 返回 (gcd)<br /> <br /> .子程序 gcd3, 整数型, , 更相减损法<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> <br /> .如果真 (a ＝ b)<br />     返回 (a)<br /> .如果真结束<br /> .如果真 (a ＜ b)  ' 保证a>=b<br />     交换变量 (a, b)<br /> .如果真结束<br /> 返回 (gcd3 (b, a － b))<br /> <br /> <br /> .子程序 gcd4, 整数型, , 欧几里德算法<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> <br /> .如果真 (b ＝ 0)<br />     返回 (a)<br /> .如果真结束<br /> 返回 (gcd4 (b, a ％ b))<br /> <br /> <br /> .子程序 _MIN, 整数型<br /> .参数 a, 整数型<br /> .参数 b, 整数型<br /> <br /> .如果真 (a ＜ b)<br />     返回 (a)<br /> .如果真结束<br /> 返回 (b)

全部代码下载：
求最大公约数.e (5.44 KB, 下载次数: 13)

2022-10-3 10:04 上传

点击文件名下载附件
效果图：

youxigw

支持开源~！感谢分享

沈远

源码回复可见

czy731

学习学习，

lxh628

支持开源~！感谢分享

象山海鲜

支持开源~！感谢分享

yxl2008

谢谢分享！！

汉族

感谢分享  

jing2020yi

谢谢分享~

风清云游

看看 支持一下