유클리드 호제법

유클리드 호제법

- 최대공약수를 간단하게 구할 수 있는 알고리즘

설명

1. 둘 중 더 큰 수를 구별
2. 둘을 나눠서 나머지가 0이 될 때까지 계속 나눔
2-1 나눴는데 나머지가 0이 아니면 작은 수랑 나머지랑 나눔
2-2 이것을 나머지가 0이 될 때까지 반복

코드

function solution(n, m) {
    let big = n < m ? m : n;// 둘 중 더 큰 수 비교
    let small = n < m ? n : m;// 작은 수
    let $gcd = gcd(big, small);
    return [$gcd, big*small/$gcd];
}
//최소공배수(lcm) = 큰 수* 작은 수 / 최대공약수


function gcd(a,b) {
    return b ? gcd(b,a%b) : Math.abs(a);
  //b(나머지)가 0이면 절댓값(a)반환
  //b가 0일때까지 재귀반복
}