[Math] 최대공약수와 최소공배수 이론 및 문제풀이

---

1. 약수와 배수 정의

• 공약수 : 두 정수의 공통 약수를 공약수라고 한다. 
• 공배수 : 두 정수의 공통 배수를 공배수라고 한다.

---

2. 최대공약수와 최소공배수 정의

• 최대공약수[GCD} : 두 정수의 공약수 중 가장 큰 것을 최대공약수라고 한다.
• 최소공배수[LCM] : 양의 공배수 중 가장 작은 것을 최소공배수라고 한다.

https://terms.naver.com/entry.naver?docId=5696053&cid=47324&categoryId=47324

위의 식을 보면 최소공배수를 구할때 최소공약수만 계산하면 쉽게 구할수 있는것을 알수 있다. 특히 최소 공약수의 경우

유클리드 호제법을 사용하면 소인수분해를 하지 않고도 계산이 가능하다. 

최소 공배수와 최대 공약수의 관계

---

4. 유클리드 호제법

유클리드 호제법은 두 수의 최대 공약수를 구할 때 사용하는 방법이다. 일반적으로 최대 공약수를 구할때는 소인수 분해를 이용한 공통된 소수들의 곱으로 표현하지만 유클리드 호제법은 MOD연산을 사용한다. 

https://scienceland.info/en/algebra8/euclid-algorithm

다음과 같이 나머지가 0이 될 때까지 나눗셈이 반복하면 GCD는 마지막 나눗셈의 값이 된다.

def gcd(a, b):
  if b == 0 :
    return a
  else :
    return gcd(b, a % b)
        
print(gcd(3214,322))
>>> 2

---

최대공약수와 최소공배수

프로그래머스

---

분수의 덧셈 (최대공약수와 최소공배수 응용)

프로그래머스

---