Post

Euclidean Algorithm

유클리드 알고리즘에 대해 설명하는 페이지입니다.

Posted
Preview Image
By HyunJinNo
1 min read
Euclidean Algorithm

Tags
Algorithm

Introduction

  • Definition
    • 유클리드 알고리즘(Euclidean Algorithm)) 은 두 수의 최대공약수를 구하는데 사용되는 방법입니다.
    • 유클리드 알고리즘은 두 수 a, b(a > b)의 공약수의 집합은 (a - b)와 b의 공약수 집합과 같다는 점을 이용합니다. 즉, a, b의 최대공약수 gcd(a, b)는 항상 (a - b)와 b의 최대공약수 gcd(a - b, b)와 같습니다.

How to Use

최소 공배수

1
2
3
4
5
6
7
8

// Java
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

1
2

// Kotlin
fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

1
2
3
4
5
6
7
8
9
10
11

/**
 * @param {number} a
 * @param {number} b
 */
const gcd = (a, b) => {
  if (b === 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
};

최대 공약수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * @param {number} a
 * @param {number} b
 */
const gcd = (a, b) => {
  if (b === 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
};

const a = 21;
const b = 15;

const lcm = (a * b) / gcd(Math.max(a, b), Math.min(a, b));

Examples

Algorithms
algorithm
This post is licensed under CC BY 4.0 by the author.