最大公约数和最小公倍数

这篇也是闹着玩的,随便看看吧😅

最大公因数

最大公约数,也叫最大公因数,英语(Greatest Common Divisor,GCD),指的能够整除多个整数的最大正整数,而多个整数不能为零,经典例子:8和12的最大公因数为4

求最大公因数的主要方法:

列举法:列举出两整数的因数,并找出最大公因数

质因数分解:分别列出两数的质因数分解式,并计算共同项的乘积

短除法:两数除以相同的质因数,直到两数互质时,所有除数的乘积即为最大公因数

列举法

列举法很简单,一个一个列出来,但到了大的式子会显得很麻烦

举个例子,手头上有15和75分别使用列举法求公因数和最大公因数

做法如下,首先把它们的因数求出来,所有数字的因数必定包括1和数字本身,计算必定是从1开始,从1开始顺序计算

15:1, 3, 5, 15(15=1×15,3×5,5×3,15×1)
75:1, 3, 5, 15, 25(75=1×75,3×25,5×15)

把因数找出来后,将他们排好找出相同的数字,如1、3、5和15,这就是他们的公因数,然后找出他们最大的公因数就行,15就是他们最大的公因数

程序实现

再举个例子,54和24的最大公因数,步骤和上面差不多一样,这里我直接用程序跑

短除法

短除法首先要找出数的质因数,然后再将质因数进行相乘,很简单的,看下面的图吧,但到了比较大的数时,如15484和21511要找出它们的最大公因数,是非常耗时间的。为此可以通过辗转相除法找出最大公因数

质因数分解法

质因数分解法,先将每个数进行质因数分解,比如我们要分解12和8,12=$2^2×3$,12的质因数有2和3,而8可以写成$2^3$,8的质因数只有2,接下来把它们相同的数字列出来,然后进行相乘,$2×2$,所以12和8的最大公因数为4,这么写可能有点怪,画图会好理解些。

找出他们的质因数之后,排在一块找出相同的数字然后进行相乘。

总而言之就是将两个数的质因数共同的质因数进行相乘

辗转相除法

辗转相除法又叫做欧几里得演算法

小数当作除数,大数当作被除数,再将求出来的商乘上较小的数,然后再减掉大数,求出它的余数,再接着把余数当成新的除数,相反原来的数就变成被除数,将两数相除,得出来的数再乘以刚才的除数,得出一个新的数,再将这两个数相减,然后依次类推,直到没有余数(得到0),那就是他的最大公因数,相比于上述两种方法,这种效率更高

比如我们要用辗转相除法求出 (18和48) 的最大公因式,步骤如下:

由此可推导出一个公式 $a = b * Q(商数) + R(余数)$ ,假设 $ (a,b) =(b,r) $,将上述两个数套入公式具体步骤如下

挺简单的,比如计算gcd(18, 48)时,我们可以通过画图来解

再举几个例子把,比如计算gcd(8, 12),使用辗转相除法进行计算

拓展

这题网上找的,步骤看了作业帮的,不然根本做不出来,我太菜了,lol

程序实现

def gcd_ojld(a, b):
     m = max(a, b)
     n = min(a, b)
     t = m % n
     while True:
          if t != 0:
               m = n
               n = t
               t = m % n
               print(n)
print("GCD Is:")
print(gcd_ojld(26, 36))

最小公倍数

最小公倍数(Least Common Multiple),假设一个数x,可以被另外两个数A和B整除,且X大于(或等于)A和B,则X为A和B的公倍数,A和B的公倍数有无限个,而所有的公倍数中,最小的公倍数就叫做最小公倍数

与最大公因式的关系 $lcm(a, b) = \frac {|a*b|}{gcd(a, b)}$

原理和上面差不多,无非就是将所有的质因数相乘,自己理解即可

程序实现

def gcd(a, b):
     return a if b == 0 else gcd(b, a % b)
def lcm(a, b):
     print(a*b / gcd(a, b))
print("GCD Is:")
print(gcd(12, 18))
print("LCM Is:")
print(lcm(12, 18))

参考资料

歐幾里得演算法(輾轉相除法) – YouTube

最小公倍數 – 維基百科,自由的百科全書 (wikipedia.org)

輾轉相除法 – 維基百科,自由的百科全書 (wikipedia.org)

最大公因數 – 維基百科,自由的百科全書 (wikipedia.org)

文章《最大公约数和最小公倍数》采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可

评论

  1. Yumewow
    iPhone Safari 12.1.2
    9月前
    2020-12-20 15:42:19

    ? err:gcd(15 ,75)==5 // true

    • 欧阳熊和 博主
      Windows Edge 87.0.664.66
      9月前
      2020-12-20 15:49:05

      lol

  2. Yumewow
    iPhone Safari 12.1.2
    9月前
    2020-12-20 16:02:28

    line:列举法倒数第一行75和15的公因数应改为15?
    实现:range终值少了一个判断——b>a?

    • 欧阳熊和 博主
      Windows Edge 87.0.664.66
      9月前
      2020-12-20 16:09:15

      啊,写错了 lol 马上改

  3. Yumewow
    iPhone Safari 12.1.2
    9月前
    2020-12-20 16:09:06

    这个vb内a mod 0会终止程序….
    细节捕捉….理解的差不多了

    • 欧阳熊和 博主
      Windows Edge 87.0.664.66
      9月前
      2020-12-20 16:14:15

      刚开始用vb实现的😂,后来直接用py了,怪不得出错

  4. Yumewow
    Windows Firefox 81.0
    9月前
    2020-12-20 18:54:50

    小心你的列举法:建议循环之前添加如下判断设置正确的循环次数
    bigger = b>a+1 ? b+1 : a+1

    • Po7mn1
      Windows Edge 87.0.664.66
      9月前
      2020-12-20 19:01:24

      收到

  5. Yumewow
    Windows Firefox 81.0
    9月前
    2020-12-20 20:20:04

    vb运行b mod a之前先判断a0
    复用参数来代替min(),max()
    let remainder = a;
    if (a > b) {
    a = b; b = remainder;
    }
    if( b %a = 0) return b; // 自身就是最大公因数
    while ….

    • Yumewow
      Windows Firefox 81.0
      9月前
      2020-12-20 20:24:22

      try this:

      def gcd(a, b):
      return a if b == 0 else gcd(b, a % b)
      gcd(1,100)

      // that returns 1

      理解起来确实简单,实现起来小坑比较多,设计(发现这个规律)的数学家真是个天才

      • 欧阳熊和 博主
        Windows Edge 87.0.664.66
        9月前
        2020-12-20 20:30:00

        yea,Complete done!

  6. Yumewow
    Windows Firefox 81.0
    9月前
    2020-12-20 22:22:04

    感觉这个短除法跟质因数没差,都要寻找质因数嘛(2,3,5,7这四个质因数就可应对所有自然数了)

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: www.bilibili.com
Source: ななひら
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
嘉然
ななひら
小恐龙
花!
上一篇
下一篇