[파이썬] 최대공약수/최소공배수 구하기 - 유클리드 호제법

파이썬으로 최대공약수와 최소공배수를 구하는 알고리즘입니다. 

 

최대공약수는 유클리드 호제법을 사용하여 구하며, 최소공배수는 최대공약수*(첫 숫자/최대공약수)*(두 번째 숫자/최대공약수)라는 점을 이용합니다.

 

최대공약수 | 20, 4 -> 4

---

def gcd(m:int,n:int):    # gcd : 최대공약수를 뜻합니다. (greatest common divisor)
    if n > m:            # m은 n보다 큰수이어야 합니다. 만약 아니면
        m, n = n, m      # m과 n을 바꾸어 줍니다.
    while n != 0:
        if m%n == 0:         # m을 n으로 나눈 나머지가 0이면 n을 리턴합니다.
            return n
        else:
            m, n = n, m%n    # m을 n으로, n을 m을 n으로 나눈 나머지로 정합니다.
    return m                 # 만약 n이 0이면 m을 리턴합니다.
    

if __name__ == '__main__':
	a = int(input('첫번째 숫자 : '))     # m과 n을 입력받습니다. (정수가 아닐경우 오류가 발생합니다.)
	b = int(input('두번째 숫자 : '))
	print(gcd(a, b))					# 최대공약수를 구한 후 출력합니다.

 

 

최소공배수 | 20, 4 -> 20

---

def gcd(m:int,n:int):
    if n > m:
        m, n = n, m
    while n != 0:
        if m%n == 0:            # 위쪽 참고
            return n
        else:
            m, n = n, m%n
    return m

def lcm(m:int,n:int):		# lcm : 최소공배수를 뜻합니다. (least common multiple)
    lcm_gcd = gcd(m, n)
    return int(lcm_gcd * (m / lcm_gcd) * (n/lcm_gcd))	# 최소공배수를 구합니다.


if __name__ == '__main__':
	a = int(input('첫번째 숫자 : '))     # m과 n을 입력받습니다. (정수가 아닐경우 오류가 발생합니다.)
	b = int(input('두번째 숫자 : '))
	print(lcm(a, b))					# 최소공배수를 구한 후 출력합니다.