[알고리즘/Algorithm] 최대 공약수, 최소 공배수 공식 유클리드 호제법 알아보기

파이썬으로 백준 2609번 최대공약수와 최소공배수 문제(아래 링크)를 풀던 중, 많은 사람들이 최대 공약수와 최소 공배수를 특정한 공식으로 풀고 있던 것을 발견했다.

 

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

찾아본 결과 그 공식은 '유클리드 호제법' 이라는 공식이였고, 아주 멋진 공식 같아서 좀 더 알아보기로 했다.

 

네이버 백과사전에 의하면 아래와 같이 정의되어 있다.

출처 : https://terms.naver.com/entry.naver?docId=2073670&cid=47324&categoryId=47324

솔직히 뭔 소린지 하나도 모르겠다..

 

그래서 우선 공식을 외우기로 했다!

때로는..

처음부터 모든 것을 이해하려고 노력하기 보다는 일단 무작정 외워서 사용하며 손에 익히는 것이 더 좋은 방법일 때가 있다..

 

이 공식을 파이썬으로 나타내면 아래와 같이 나타낼 수 있다.

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


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

참고로 gcd와 lcm은 순서대로 최대 공약수, 최소 공배수를 나타낸다.

• gcd : Greatest common divisor (최대 공약수)
• lcm : least common multiple (최소 공배수)

 

파이썬으로 공식을 나타내면 생각보다 이해하기가 어렵지는 않다.

 

gcd 함수에 숫자 2개를 넣으면 그 숫자 2개에 대한 최대 공약수를 얻을 수 있고,

lcm 함수에 숫자 2개를 넣으면 그 숫자 2개에 대한 최소 공배수를 얻을 수 있다.

 

 

참고

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