🌱 유클리드 호제법

---

자연수 a,b에 대해서 a와 b를 나눈 나머지를 r이라 한다면, a,b의 최대 공약수와 b,r의 최대 공약수는 같다.

• 최대 공약수(GCD) 찾기

  192와 72의 최대 공약수를 찾는 경우

  192/72는 약분하면 8/3이 됨

  192 % 72 = 48
  72 % 48 = 24
  48 % 24 = 0

  둘 중 한 값을 나머지 값으로 계속 mod 연산하면 0이 된다.
  여기서 0이 될 때 나눈 값이 최대 공약수가 됨

• Code

	public static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

• 최소 공배수(LCM) 찾기

  LCM = (a * b) / GCD

Referecne URLs :

• https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95
• https://programmer-chocho.tistory.com/9
• https://rok93.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-GCD-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98