合信论坛

快捷导航
查看: 8698|回复: 0

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

[复制链接]

8

主题

9

帖子

182

积分

注册会员

Rank: 2

积分
182
发表于 2021-9-22 14:19:02 | 显示全部楼层 |阅读模式

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

1 短除法

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

短除法.png


2 欧几里得算法

欧几里得算法(英语:Euclidean algorithm),又称 辗转相除法,是求最大公约数的算法。
辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。
辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。
辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252 和 105 的最大公约数是 21;因为 252 − 105 = 21 × (12 − 5) = 147 ,所以 147 和 105 的最大公约数也是 21

辗转相除.png

/*************************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);


}










您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

客服热线
400-700-4858 周一至周五:09:00 - 18:00
深圳市南山区打石一路深圳国际创新谷6栋A座9层

深圳市合信自动化技术有限公司(简称“合信技术”)成立于2003年,高新技术企业,专注于工业自动化产品的研发、生产、销售和技术服务,依靠高质量、高性能的自动化控制产品与方案为客户创造最大价值,立志于成为全球领先的工业自动化解决方案供应商。

Archiver|手机版|小黑屋|COTRUST Inc. ( 粤ICP备13051915号 )

GMT+8, 2024-3-28 17:02 , Processed in 0.092374 second(s), 23 queries .

快速回复 返回顶部 返回列表