백준 2609 문제 풀이 : 최대공약수와 최소공배수 구하는 알고리즘

최대공약수(GCD)

📖 최대공약수란?

두 수의 공통 약수 중 가장 큰 값을 **최대공약수(GCD)라고 한다.

구하는 방법

📌 유클리드 호제법

1. 두 수 중 큰 수를 작은 수로 나눈 나머지를 구한다.
2. 작은 수와 나머지로 다시 1번 과정을 반복한다.
3. 나머지가 0이 되면, 나누는 수가 최대공약수(GCD) 입니다.

📌 이미지로 이해하기

📝 코드 (암기 추천!)

def gcd(a, b):
    while b !=0:
        a, b = b, a % b
    return a

---

최소공배수(LCM)

📖 최소공배수란?

두 수의 공통 배수 중 가장 작은 값을 최소공배수(LCM) 라고 한다.

구하는 방법

최소공배수는 최대공약수를 이용하여 다음과 같이 구할 수 있다.

def lcm(a, b):
    return (a * b) // gcd(a, b)