TIL20-01 최대공약수, 최소공배수

• 문제설명 (최대공약수와 최소공배수)
  두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
• 풀이 과정
  • 최대 공약수는 두 수의 약수들 중 공통된 소수들의 곱으로 생각했다.
  • 최소 공백수는 두 수가 나누어 떨어질 때, 두 수 중 큰 수와 몫의 곱이라 생각했고, 나누어떨어지지 않을때는 두수의 곱이라고 생각했다.
  • 이 과정을 처리하기 위한 과정이다.
    1. 두수의 약수를 구하기
    2. 공통된 소수 찾기
    3. 공통된 소수의 곱 구하기
    4. 두 수를 나누어 떨어지는지 판단하기
    5. 나누어 떨어질 때 큰 수와 몫을 곱하기
    6. 나누어 떨어지지 않을 때 두수를 곱하기.
  • 이 많은 과정을 처리하려니 시간이 오래 걸렸다.
  • 아래가 완성 코드이다. 하지만 테스트 결과 실패가 나왔다.

function solution(n, m) {
    let a = []; //n의 약수 받을 배열
    let b = []; //m의 약수 받을 배열
    let answer = [];
    for ( let i =1; i <=1000000; i++ ) {
        if ( n % i === 0) {
             a.push(i);      
        }
        if ( m % i === 0) {   //약수는 나누어 떨어지는 수들이므로 나누어 떨어지는 각각의 수를 배열에 넣는다.
             b.push(i);
        }
    }
    let c = a.filter ( (x) => isPrime(x) == true  );  //약수 중 소수를 판별해 배열로 반환한다.
    let d = b.filter ( (x) => isPrime(x) == true  );
    answer.push(c.filter((x) => d.includes(x))   // 주어진 두 수의 소수 배열 중 겹치는 걸 가져온다.
                 .reduce((a,b) => a*b ,1)); //겹치는 소수를 곱하면 최소공약수가 된다.
    if ( m >= n) {
        if ( m%n === 0){
            answer.push(parseInt(m/n) * n);  // 두 수 중 큰수를 분모로 작은수를 분자로 했을 때
    } else {                                 // 나누어 떨어지면 그 몫과 작은수를 곱하면 최소공배수이고,
            answer.push( m * n);            // 나누어 떨어지지 않으면 두 수의 곱의 최소공배수가 된다.
        }        
    } else if ( n >= m ) {
        if ( n % m === 0) {
            answer.push(parseInt(n/m) * m);
        } else {
            answer.push ( n * m);
        }        
    } 
    return answer.sort((a,b)=> a-b);   
}
function isPrime(num) {
    // 소수는 1과 자기 자신만으로만 나누어 떨어지는 수 임으로
    // num > i
    for(let i = 2; num > i; i++) {
    if(num % i === 0) { //이 부분에서 num이  다른 수로 나눠떨어진다면 소수가 아님
      return false;
     }
    }
   // 소수는 1보다 큰 정수임으로
   // 1보다 작으면 false를 리턴한다
   return num > 1;
  }
console.log(solution(500,5000));

• 풀이 과정에서 사고 과정이 복잡했고, 그 결과 코드가 너무 길어지고, 예외를 너무 만드는 결과를 초래했다. 그래서 다른 사람의 풀이를 참고했고, 의외로 간단한 풀이 과정임을 깨달았다.
  • 최소 공약수는 두 수의 공통된 약수 중 가장 큰 정수이다.
  • 최소 공배수는 두 수의 공통된 배수 중 가장 작은 정수이다.
    1. 공통된 약수이므로 두 수와 동시에 나누어 떨어지는 정수 중 큰 수를 구하면 된다.
    2. 공통된 배수이므로 두 수와 동시에 나누어 떨어지는 정수 중 가장 작은 수를 구하면 된다.
  • 아래는 위의 내용을 반영한 코드이다.

function solution(n, m) {
        let a = 1;
        for ( let i =2; i <= Math.min(n,m); i++) { //최대공약수는 두 수의 공통된 약수 중에 가장 큰 정수이다.
            if ( n%i === 0 && m%i=== 0) {
                a = i;
            } 
        }
        let b = 1; 
        for ( let i = 1; i<=n*m; i++) {
            if ( i%n === 0 && i%m ===0) {  //최소공배수는 두 수의 공통된 배수 중 가장 작은 수이다.
                break; // 첫번째 공통 배수가 나오면 반복을 멈춘다.
            } b++;
        }
        return [a,b].sort((a,b) => a-b);
  }