[CodingTest]GCD & LCM

최대공약수(Greatest Common Divisor, GCD)

공통된 약수 중 가장 큰 숫자

공약수(Common Divisor)

---

공통된 약수

---

최소공배수(Lowest Common Multiple, LCM)

공통된 배수 중 가장 작은 숫자

공배수(Common Multiple)

공통된 배수

---

구하는 방법(가장 작은 수들의 곱)

12 = 2 x 2 x 3
18 = 2 x 3 x 3

2 x 3 x 3 x 2 = 36

겹치는 부분인 2와 3을 곱한 수인 6이 최대공약수

6을 중심으로 2와 3을 곱해 나오는 수인 36이 최소공배수

---

구하는 방법(유클리드 호제법)

---

2개의 자연수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 나머지가 0이 되었을 때 나누는 수