정수론 - 최대공약수, 최소공배수 (유클리드 호제법)

유클리드 호제법이란

주어진 두 수 사이에 최대공약수를 구하기 위한 알고리즘이다.

이를 통해 최대공약수를 구하면 최소공배수 역시 쉽게 구할 수 있다. 

 

두 수 A, B가 있다고 하자. 그리고 r은 A를 B로 나눈 나머지(A%B) 라고 하자. 

유클리드 호제법은 A, B, r 세 수를 가지고두 단계를 반복하는 것이다. 

step1. A를 B로 나누어 r을 만든다. 

step2. r이 0이면 이 때의 B가 최대공약수이고, r이 0이 아니면 B의 값은 A가, r의 값은 B가 되어 step1~step2를 반복한다. (언제까지?? r이 0이 되어서 B라는 최대공약수를 구할 때까지)

구현

위의 방법을 구현하는 방식은 2가지가 있다. 

1) 반복문을 이용한 방법

while(1){
    let r = A%B;
    if(r===0){
    	return B
     }
     A = B;
     B = r;
}

2) 재귀를 이용한 방법 

function getGcd(A, B){
	if(A%B === 0){
    	return B;
    }
    return getGcd(B, A%B);
}

유클리드 호제법으로 최대공약수(GCD)를 구했다면, 최소공배수(LCM)를 구하는 방법

두 수 A, B가 있었다면 
A = 위에서 구한 GCD * α

B = 위에서 구한 GCD * β 

로 구성되어 있었을 것이다. 

그러면 A의 배수이면서 동시에 B의 배수인 것 중 가장 최소인 최소공배수(LCM)는

LCM   =  GCD * α * β 

즉,      =  A* β  = B * α  

따라서 = (A*B) / GCD  이다.  

 

이를 코드로 구현하려면, 

let originA = A;
let originB = B;
let GCD;

while (1) {
    let r = A % B;
    if (r === 0) {
      GCD = B;
      break;
    }
    A = B;
    B = r;
}

let LCM = (originA * originB)/GCD

※ A와 B는 while문 안에서 유클리드 호제법을 할 때 이리저리 값이 바뀌므로 LCM을 구할 때 필요한 원래 A, B 값은 originalA, originalB로 보존해 놓는 것이 좋다. 

예제

문제.
Write a function that takes a number as its argument and returns a string that represents that number's simplified fraction.
Example: toFraction(0.5) === '1/2'
Whole numbers and mixed fractions should be returned as irregular fractions
Example: toFraction(3.0) === '3/1'
Example: toFraction(2.5) === '5/2'

코드.

var toFraction = function (number) {
  //1. number을 정수로 만들어주기 위한 최소번 10을 곱한다.
  let denominator = 1;
  let len = String(number).length;
  for (let i = 1; i <= len - 2; i++) {
    number *= 10;
    denominator *= 10;
  }
  number = Math.floor(number); //이건 testcase중 toFraction(0.253213)의 0.253213는 이상하게도 0.25321300000000003으로 인식되는 경우 때문이다..

  //2. 이렇게 되면 정수가 된 number와 10의 거듭제곱으로 만들어진 분모 denominator가 생긴다.
  // 그러면 이것의 최대공약수를 구해서, 둘을 나눈뒤 기약분수화 시킨다.
  // 최대공약수를 구하는 방법은 <유클리드 호제법>을 사용한다.
  let originNumber = number;
  let originDenom = denominator;
  let GCD;

  while (1) {
    let r = number % denominator;
    if (r === 0) {
      GCD = denominator;
      break;
    }
    number = denominator;
    denominator = r;
  }
  //3. 이렇게 구해진 최대공약수인 GCD를 분모(dennominator)와 분자(number)에 각각 나눠서 기약분수로 만든다.
  //단, number와 denominator는 GCD를 구하는 과정에서 값이 이리저리 바뀌었으니 미리 원본을 빼놓은 originNumber, originDenom를 이용한다.

  return `${originNumber / GCD}/${originDenom / GCD}`;
};