[Python] 최대공약수, 최소공배수

최대 1 분 소요

🙄 간단한 함수에 대해 알아보기 전 최대공약수를 구하기 위해 많이 사용되는 유클리드 호제법에 대해 짚고 넘어가자!

👩 유클리드 호제법 : 최대공약수 구하기

유클리드 호제법이란 나눗셈을 반복해서 두 수의 최대공약수를 구하는 알고리즘이다.

그 과정은 다음 코드를 통해서 자세히 살펴보자!!

아래는 a, b의 최대공약수를 구하는 과정이다.

  def gcd(x, y):
    while(y):
      x, y = y, x%y
    return x

  print(gcd(a, b))

여기서 핵심은 다음과 같다!

x, y의 최대공약수 = y, (x%y)의 최대공약수

x%y = 0이 되었을 때의 x와 y의 최대공약수가 최초의 a, b의 최대공약수와 동일하게 된다.
이때 x%y = 0일 경우, x >= y이므로 y가 최대공약수가 된다.
- 단, 반복문에서는 x, y = y, x%y로 인해 x가 최대공약수가 된다.

이렇게 구한 최대공약수를 가지고 우리는 쉽게 두 수의 최소공배수를 구할 수 있다.

(a*b)//최대공약수 = 최소공배수

def lcm(x, y):
  return (x*y)//gcd(x, y)

🙄 어떤가 간단하지 않은가!! 그렇다면 오늘의 하이라이트!! math 모듈 속 lcm, gcd를 마지막으로 살펴보자!

  print(math.gcd(22, 11, 77)) # 11
  print(math.lcm(11, 33, 99)) # 99