iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
自我挑戰組

一個月的演算法挑戰系列 第 29

Day29:輾轉相除法(Euclidean algorithm)

輾轉相除法(Euclidean algorithm)

輾轉相除法是求兩數的最大公因數(greatest common divisor,GCD)的演算法,也被稱為「歐幾里德演算法」(歐式演算法),輾轉相除法只要反覆進行除法,就能求出最大公因數。即使運算的兩個數很大,也能用明確步驟有效率地求出最大公因數。

使用Python實現GCD

方法1:

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

方法2:

import math

print(math.gcd(1071,462)) #21

使用JavaScript實現GCD

function gcd(x, y) {
 if ((typeof x !== 'number') || (typeof y !== 'number')) 
    return false;
  x = Math.abs(x);
  y = Math.abs(y);
  while(y) {
    var t = y;
    y = x % y;
    x = t;
  }
  return x;
}

上一篇
Day28:網頁排名演算法(PageRank)
下一篇
Day30:總結
系列文
一個月的演算法挑戰30

尚未有邦友留言

立即登入留言