专栏首页数值分析与有限元编程算法 | 求最大公约数和最小公倍数

算法 | 求最大公约数和最小公倍数

小学数学就学习了如何计算最大公约数(Greatest Common Factor,GCF)和最小公倍数(Lowest Common Multiple,LCM)。例如15和25的最大公约数是5,最小公倍数是75,数学老师会不厌其烦的用质数分解的方法讲解。那么,能不能用计算机来算?古希腊数学家欧几里得提出了最大公约数GCF的算法:

给出两个整数A和B

if B==0

则答案是A

else

答案是GCF(B,A%B)

这里%是取余运算,A%B的意思是A除以B,返回余数。例如5%2返回1,4%2返回0,即4能被2整除。

以上算法的大致思路是:如果B不等于0,则转为求B和A%B的最大公约数,并通过递归调用。来看一个例子

求35和25的最大公约数,过程如下表

有了求GCF的算法,求LCM就很简单了。求LCM关键是找到最大公约数GCF,算法如下

n=GCF(A,B)

LCM(A,B)=n*(A/n)*(B/n)

或者LCM(A,B)=A / n * B

用Fortran来实现

欧几里得的《几何原本》(Elements)是西方文明史上最有名气的著作之一,古往今来都作为标准教科书使用,书中展现了他大师级的逻辑推理。事实上,“证明题”就源自他的《几何原本》。该著作对后世的数学家和哲学家产生了深远影响。

本文分享自微信公众号 - 数值分析与有限元编程(program_fem),作者:苦丁茶123

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 严格对角占优矩阵

    定义:对于一个n阶方阵A,主对角元素的绝对值大于该行其余元素的绝对值之和,即|aii|>Σ|aij| ( j /= i )。则称矩阵A是严格对角占优矩阵。对列同...

    fem178
  • 数值积分|高斯积分

    如图a所示。这样当然会造成很大的误差。如果在区间内部找两个点,且通过这两个点的直线与区间端点构成的梯形面积最大限度地接近精确值,即图b中A1+A2=A3,这就是...

    fem178
  • 用随机数模拟生日悖论问题

    生日“悖论”其实并不是悖论,它是说在一个人数超过23人的集体中,至少有两个人生日在同一天的概率会大于0.5。因为这个理论上的概率与人们的直觉不符,才会被称为“悖...

    fem178
  • Power Pivot智能日期运用——连续时间(2)

    返回2018/2/1-2018/6/31日的时间列,但是因为6月份只有30天,所以会自动顺延一天,实际返回的是2018/2/1-2018/7/1的时间列。

    逍遥之
  • pycharm管理断点怎么删除断点

    3、进行点击了run菜单之后弹出了下拉菜单选中为 view breakpoints 的选项

    于小勇
  • 【处理手记】Configuration system failed to initialize异常的另类原因

    度娘一番,发现市面上常见的原因是配置文件中的特定节点的位置不对,或者配置文件损坏等等,而这个程序根本没有使用内置的配置文件方案,而是用的ini,所以不适用我的问...

    AhDung
  • Power Pivot中DAX的时间函数

    如果数据模型的日期范围是2018/5/1—2019/6/30,则生成的日期表范围为2018/1/1—2019/12/31

    逍遥之
  • 了解递归策略网络的有限状态表示(CS LG)

    本文中,我们介绍了一种理解递归策略网络有限状态机(FSM)表示的方法。最近的研究成果大都集中在最小化FSM来获得高层次的洞察力,然而,最小化会通过合并语义上不同...

    Elva
  • 12.Elasticsearch查询关键字3

    目录: - 1._validate - 2.explain - 3.rewrite

    IT云清
  • QT--QSocketNotifier类介绍

    QSocketNotifier 用来监听系统文件操作,将操作转换为Qt事件进入系统的消息循环队列。并调用预先设置的事件接受函数,处理事件。

    morixinguan

扫码关注云+社区

领取腾讯云代金券