EuclideanGCD [辗转相除法]

# 介绍

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

# 原理

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如 21 = 5 × 105 + (−2) × 252 。这个重要的结论叫做裴蜀定理。两个数的最大公约数通常写成 GCD (a, b)。

在现代密码学方面，它是 RSA 算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。辗转相除法是现代数论中的基本工具。

EuclideanGCD

# 实现

# JavaScript

/*
Calculates GCD of two numbers using Euclidean Recursive Algorithm
:param first: First number
:param second: Second number
:return: GCD of the numbers
*/
function euclideanGCDRecursive (first, second) {
  if (second === 0) {
    return first
  } else {
    return euclideanGCDRecursive(second, (first % second))
  }
}

/*
Calculates GCD of two numbers using Euclidean Iterative Algorithm
:param first: First number
:param second: Second number
:return: GCD of the numbers
*/
function euclideanGCDIterative (first, second) {
  while (second !== 0) {
    const temp = second
    second = first % second
    first = temp
  }
  return first
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 参考

编辑

上次更新: 2022/06/20, 20:15:04

← BinarySearch [二分搜索] Factorial [阶乘]→