GCD의 고찰 (최대공약수)

1.최대공약수 개념

2.코드 표현법

유클리드 호제법: Euclidean algorithm

알고리즘의 피타고라스의 정리 아닐까 싶을정도로

이건 알고 넘어가자

일단 코드 부터 보면서 해보자

function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}

두수가 입력이 되면

나머지가 0이 된다면 n 을 출력하고
0이 안된다면
재귀함수에 자리를 바꾸고, 나머지를 넣어줘라

그리고 나눠떨어지면 그것이 최대공약수 임;

삼항연산자로 표현도 가능함

const gcd = (m, n) => m % n === 0 ? n: gcd(n, m % n);

function divideChocolateStick(M, N) {
  // TODO: 여기에 코드를 작성합니다.

  //최대공약수 찾는 함수
  const GCD = (m, n) => {
    if(m % n === 0) return n;
    else return GCD(n, m % n);
  }
  let result = [];

  //인원수를 차례대로 늘려가면서 구한다. 
  // 최대공약수 까지만.
  // 나아가 제곱근까지만 구하는 반복도 가능하다.
  const gcd = GCD(M,N)



  for(let i = 1; i <= Math.floor(Math.sqrt(gcd)); i++){
    if(gcd % i === 0){
      result.push([i, M / i, N / i])
      if(i * i < gcd)
        let j = gcd / i
        result.push([j, M / j, N / j])
    }
  }
  return result;
}

function divideChocolateStick(M, N) {
  // TODO: 여기에 코드를 작성합니다.
  const GCD = (M,N) => {
    if(M % N === 0){
      return N;
    } else {
      return GCD(N , M % N)
    }
  }

  const gcdNum = GCD(M,N)

  let result = [];
  let sqrt = Math.floor(Math.sqrt(gcdNum));
  //여기서 i는 사람임
  for(let i = 1; i <= sqrt; i++){
    if(gcdNum % i === 0){
      result.push([i , M / i, N / i]);
      if((i * i) < gcdNum){
        const j = GCD(M,N) / i 
        result.push([j , M / j, N / j])
      }
    }
  }
  result.sort((a,b) => a[0] - b[0])
  return result;
}