알고리즘 - 최대공약수, 최소공배수 유클리드 호제법

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

https://programmers.co.kr/learn/courses/30/lessons/12940

function gong(n, m) {
  // 최대공약수 : 두 수의 공통되는 약수 중에서 제일 큰 수
  // 최소공배수 : 두 수의 공통되는 배수 중에서 제일 작은 수
  const biggest = n > m ? n : m; 
  				// = Math.max(n , m);
  // 더 큰 값을 가져올거니까 큰 거 저장
  
  let max = 0; // 공약수 중에서 제일 큰 수가 저장된다.
  
  for (let i = 1; i <= biggest; i++) {
    // console.log(i, n%i, m%i)
    if(n%i === 0 && m % i === 0) {
      console.log(i, n, m)
      // i는 n과 m의 공약수다! 헉 대박... 
      max = i;
    }
    console.log(max)
    
    
   // 최소공배수 구하기
   // 초기값이 가장 큰 값이 들어오고 i는 비기스트의 배수들을 가져오게 되는거야
    let min = 0; // 공배수 중에서 제일 작은 수가 저장된다. 
    
    for(let i = biggest; i<= n*m ; i += biggest) {
      // console.log(i % Math.min(n, m) === 0 )
      if(i%Math.min(n,m) === 0) {
        return [max, i];
        // min = i;
        // break; 
      }
    }
    return [max,min];
  }

for문으로 풀기 🥹

 

 

🥸유클리드 호제법

 a를 b로 나눴을 때 (a가 b보다 클 경우) === 큰 수에서 작은 수를 나눴을 때

나머지 값이 0이 되면 작은 수(b)가 최대공약수가 된다.

 

나머지 값이 0이 되지 않으면, 큰 수(b)에 작은 수(a)를 할당하고

작은 수(b)에는 나눴던 나머지 값을 할당한다. 

 

반복해서 나머지 값이 0이 나오면, 이때 나눴던 작은 수(b)가 최대 공약수가 된다. 

 

let a = Math.max(n,m); //큰 수

let b = Math.min(n,m); // 작은 수

let r = 0; // a를 b로 나눴을 때의 나머지 값

while((a%b)>0) {

r = a % b; // 큰 수에서 작은 수를 나눈 나머지 값을 저장

a = b; // 큰 수는 나눴을 때의 작은 수를 할당

b = r; // 작은 수는 나머지 값을 할당

// 최소공배수 구하기 : 두 수를 곱한 값에 최대공약수를 나눈 값

return [b, (n*m) / b];