최대공약수, 최소공배수 구하기 (Feat. 유클리드 호제법)

 

유클리드 호제법을 이용한 최대공약수, 최소공배수 알고리즘을 파이썬 스크립트로 알아보자.

 

최대공약수(GCD)란?

- 두 자연수의 공통된 약수 중 가장 큰 수

 

최소공배수(LCM)란?

- 두 자연수의 공통된 배수 중 가장 작은 수

최소공배수 = 두 자연수의 곱 / 최대공약수으로 구할 수 있다.

 

 

 

유클리드 호제법(Euclidean algorithm)

• 두 개의 자연수의 최대공약수를 찾는 방법

1. 큰 수에서 작은 수를 빼면 최대공약수는 변하지 않는다. 따라서 둘 중 더 큰 값을 반복해서 빼면 최대공약수가 된다. ( ex. 60, 36 ⇒ 60-36=24, 36-24=12, 24-12=12, 12-12=0. 최대공약수 12)
2. 빼기 대신 나머지를 구하다가 0이 될 때의 작은 값이 최대공약수이다. ( ex. 12, 28 ⇒ 12%28=12, 28%12=4, 12%4=0. 최대공약수 4)

 

 

파이썬 코드

코드로 아래와 같이 작성할 수 있다.

import sys

a, b = map(int, sys.stdin.readline().split())

# 최대공약수
def gcd(a, b):
  tmp = 0
  while(b != 0):
    tmp = a % b
    a = b
    b = tmp
  return a

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

print(gcd(a, b))
print(lcm(a, b))