关于最大公约数常见算法有三种：辗转相除法、更相减损法、Stein算法

其中前两种算法编写简单，过程有些类似，但是算数相差较大或数值本身较大会引起过大的计算量。最后一种算法分类复杂，但是在算数过大时可以有效的减少计算量，所以在实际使用中可以对数据判断大小选择不同方式来计算。
提示：谨防while、repeat此类循环不限次数引发的宕机，建议增加限制次数EXIT的保护。
下面介绍内容，原理证明可自行百度。

1.辗转相除法(欧几里得算法)

  gcd( a,b ) = gcd( a,a%b )；
  令a%b = c，循环求余计算
（1）c = 0，则b为最大公约数
（2）c != 0，则让a = b, b = c，执行a%b = c直到满足（1）




2.更相减损法

gcd( a,b ) = gcd( a,a-b )；
  令a、b循环相减计算
（1）a = b，则a或b就是最大公约数
（2）a != b，若a>b，则a = a-b；若a<b，则b = b-a；执行到满足（1）



3.Stein算法
  核心：奇偶分类概念
  首先规定，a>b
（1）均为偶数 gcd( a,b ) =2gcd( a/2,b/2 )；
（2）均为奇数 gcd( a,b ) = gcd( (a+b)/2,(a-b)/2 )；
（3）a奇b偶    gcd( a,b ) = gcd( a,b/2 )；
（4）a偶b奇    gcd( a,b ) = gcd( a/2,b )；

由上面不难看出，Stein算法按照奇偶性质进行2的n次方处理，即幂函数。对比相除相加的算法，幂计算在处理较大的数据时阶数逐渐降低，计算优势明显。


不论是哪种方法，都是给出了有关gcd(a,b)的性质，在实际计算中，完全可以将这些性质打乱重组灵活运用，最终目的就是快速计算出结果。


分享以学习交流为目的，如有错误请指正。

好参考，感谢分享这么好的资料

感谢分享。内容丰富

吴王 发表于 2022-6-9 13:32
用在哪儿？没用过呢，

用法不多，电子齿轮比的约分，长方形板件的裁切，单字16位长度限制分子分母数值大小

用在哪儿？没用过呢，

陌陌 发表于 2022-6-9 11:07
目前试着用ST编写这个程序，可是有一个问题，如果被除数小于除数，那么需要数值调换，可结果IF指令似乎只能 ...

习惯了C程的编程，漏打冒号了，导致直接报错

目前试着用ST编写这个程序，可是有一个问题，如果被除数小于除数，那么需要数值调换，可结果IF指令似乎只能执行BOOL类命令

感谢分享

陌陌 发表于 2022-5-31 16:36
还有一个笨办法，数字同时小于两个数字时，从1开始挨个试，如果同时满足整除取余等于零就赋值给另一个数值 ...

兄弟，穷举法太耗资源了，plc怕是吃不消哇