[자바스크립트(JavaScript)] 최대공약수, 최소공배수 구하기(유클리드 호제법)

// 최대공약수, GCD

- 반복문으로 나머지를 계산하며 최대공약수를 구할 수도 있지만 수의 크기가 클 때는 주로 유클리드 호제법을 사용한다.

* 유클리드 호제법
- 두 수 a, b가 주어졌을 때, a를 b로 나눈 나머지를 다시 b와 비교하는 과정을 반복한다.(재귀)
- 나머지가 0이 되었을 때 b가 두 수의 최대공약수가 된다.

 

const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);

---

// 최소공배수, LCM

- 두 수의 곱을 최대공약수로 나눈다.

const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
const lcm = (a, b) => a * b / gcd(a, b);

---

※ n개의 수의 최소공배수(https://school.programmers.co.kr/learn/courses/30/lessons/12953)

- 여러 개의 최소공배수를 구할 때, 먼저 2개의 최소공배수를 구한 뒤 그 최소공배수와 다음 수의 최소공배수를 구하는 방식으로 진행한다.

function solution(arr) {
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    const lcm = (a, b) => a * b / gcd(a, b);
    
    return arr.reduce((acc, curr) => {
        return lcm(acc, curr);
    }, arr[0]);
}