[JS] js로 최대공약수 최소공약수 구하기

언제 배웠는지조차 흐릿한 수학 개념을 자바스크립트로 구현해보자... 
코테로 나왔을때 이 수학 개념조차 헷갈려서 머리가 어질어질했다... 😭(수포자..집와서 검색해보니 갑자기 기억이 빡 났다)

 

우선 나처럼 개념을 까먹었었거나 혹시 모르겠다~ 할 수도 있으니 두개의 개념 설명!

 

최대 공약수 : 두 수 A와 B의 공통된 약수 중에 가장 큰 정수

최소 공배수 : 두 수 A와 B의 공통된 약수 중에 가장 작은 정수

 

6의 약수  ➡️ 1, 2, 3, 6

12의 약수 ➡️ 1, 2, 3, 4, 6, 12 

 

6, 12의 최대 공약수  ➡️ 6

 

6의 배수  ➡️ 6, 12, 24, 30, 36 ...

12의 배수 ➡️ 12, 24, 36, 48 ...

 

6, 12의 최소 공배수  ➡️ 12

 

---

 

이제 javascript 를 이용해 두 수를 입력받아, 두 수의 최대 공약수와 최소 공배수를 반환하는 함수를 만들어보자.

 

문제 : 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그 다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

문제 뜻 : 입력 받은 두 수의 최대공약수, 최소공배수를 리턴해주는 함수를 만들자

 

유클리드 호제법을 이용한 풀이 

- a,b 를 서로 나눌때, 나누어진다면 b가 최대 공약수 이다. (a>b)

- 만약 a,b가 나누어지지 않으면 b와 a를 b로 나눈 나머지를 다시 나눈다

- 서로가 나누어지면 a%b 가 최대공약수이다. 나누어지지 않는다면 위처럼 b와 a를 b를 나눈 나머지를 다시 나눈다.

const solutuon = (n, m) => {
  const gcd = (a, b) => {
    if (b === 0) return a; // 나누어지면 a 리턴
    return gcd(b, a % b); // 나누어지지 않는다면 b와 a%b를 다시 나눈다
  };
  const lcm = (a, b) => (a * b) / gcd(a, b); // 두 수의 곱을 최대공약수로 나눈다.
  return console.log(
    `최대 공약수는? ${gcd(n, m)}, 최대 공배수는? ${lcm(n, m)}`
  );
};
console.log(solutuon(6, 12));

결과

유클리드 호제법이란? 🤔

두 수의 최대공약수를 구하는 알고리즘이다. 
2개의 자연수 A,B 에 대해서 A를 B로 나눈 나머지를 r이라고 한다면 (단, A>B 이다), A와 B의 최대공약수는 B와 r의 최대공약수와 같다. 이 성질에 따라 B를 r로 나눈 나머지 r` 을 구하고, 다시 r을 r` 로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때, 나누는 수가 A와 B의 최대 공약수이다. 

 

즉, 유클리드 호제법은 나눗셈을 반복해서 최대공약수를 구할 수 있다.

해당 문제는 유클리드 호제법을 알고있다면 쉽게..풀수 있는 문제인듯 싶다.

(난 몰랐음... 히히)

 

---

한번, 각 숫자의 약수,배수를 배열로 넣어보도록 하자. 

(최소 공배수는 최대 1000으로 찍히도록..)

 

약수 구해서 배열에 넣기

function divisors(num) {
  const arr = [];
  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      arr.push(i);
    }
  }

  return console.log(arr);
}

divisors(24);

// 결과 : [2, 3, 4, 6, 8, 12]

풀이 :

약수가 되려면 나눴을 때 나머지가 0이 되어야 한다. num % i === 0; 으로 조건을 걸어두고

그걸 배열 arr 에 push 로 넣어준다.

 

 

배수 구해서 배열에 넣기

function plus(num) {
  const arr = [];
  for (let i = 0; i <= 1000; i++) {
    if (i % num == 0 && i !== 0) {
      arr.push(i);
    }
  }
  return console.log(arr);
}
plus(50);

// 결과 : [50, 100, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, 650, 700, 750, 800, 850, 900, 950, 1000]

풀이 :

1 나누기 50 -> 나머지 있음, 2 나누기 50 -> 나머지 없음... 50 나누기 50 -> 나머지 0... 이런식으로 나머지가 0으로 나눠질 때만 i 값이 출력되도록 한다.

그런데 i 값이 0일때도 출력이 되기 때문에 i가 0이 아닐때만 출력되도록 조건문을 추가해주었다. (let i = 1;) 이라고 지정해주어도 된다. 

 

 

---

어휴..프로그래머스 같은 걸 자주 풀어야 겠다...

나 코딩테스트 개노답...ㅠ