C语言欧几里得算法——求解两个数的最小公约数

星星点灯

最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。例如：18 与 12 的最大公约数为 6 。

1 短除法

短除法是求最大公因数的一种方法：先把每个数的因数找出来，然后再找出公因数，最后在公因数中找出最大公因数。

2 欧几里得算法

欧几里得算法（英语：Euclidean algorithm），又称 辗转相除法，是求最大公约数的算法。

辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252 和 105 的最大公约数是 21；因为 252 − 105 = 21 × (12 − 5) = 147 ，所以 147 和 105 的最大公约数也是 21

/*************************PLC源码*************************************/

#include "math.h"

#include "stdio.h"

#include "plc300.h"

S16 Euclid(S16 a, S16 b);

void CF_0( BOOL star, S16 dataA, S16 dataB,S16 *Commom)

{

int Variable_a=0,Variable_b=0,Variable_c=0;

                if(star)

        {

        Variable_a=dataA;

        Variable_b=dataB;

        Variable_c=Euclid(Variable_a,Variable_b);

        setS16(Commom,Variable_c);

        }

}

S16 Euclid(S16 a,S16 b)

{

        return b==0? a:Euclid(b,a%b);

}