1-1 Challenge 최소 공약수와 최대 공배수

//문제1

//두 자연수 a와 b가 주어질 때,이 둘의 최대공약수를 구하는 함수를 작성하시오.

let leastCommonDivisor = (a, b) => {

  let temp = null;

  if (a < b) {

    temp = b;

    b = a;

    a = temp;

  }

  do {

    temp = a % b;

    a = b;

    b = temp;

  } while (temp != 0);

  return a;

  //유클리드 호제법을

  //이용한 풀이

};

let greatestCommonMultiple = (a, b) => {

  let least = leastCommonDivisor(a, b);

  return (a * b) / least;

  // 두 수 곱하기 / 최소 공약수 = 최대 공배수

};

let least = leastCommonDivisor(24, 81);

let greatest = greatestCommonMultiple(81, 24);

console.log("최소 공약수 : " + least);

console.log("최대 공배수 : " + greatest);

 

 temp = 큰 수 % 작은 수 

큰수 = 작은수

작은 수 = temp

 

를 temp에 0 담길 때까지

반복하면, 

 

큰 수에 담기는 결과가 최소 공약수가 된다.

 

그렇게 구해진 최소 공약수를 이용하면,

 

큰 수 * 작은 수 / 최소 공약수

 

로 최대 공배수를 구할 수 있다.

 

 

ex) 81, 24

 

1 단계

 

temp = 81 % 24  = 9

큰 수 = 24

작은 수 = 9

 

2 단계

 

temp = 24 % 9 = 6

큰 수 = 9

작은 수 = 6

 

3 단계

 

temp = 9 % 6 = 3

큰 수 = 6

작은 수 = 3

 

4 단계

 

temp = 6 % 3 = 0

 

3이 최소 공약수가 된다.

 

그리고, 

 

81 * 24 / 3 = 648

 

이 나오는데 648이 최대 공배수가 된다!