[Python/수학] 최대공약수(GCD), 최소공배수(LCM)

최대공약수

• math 내장 함수 사용하기

math.gcd(n, m)

 

유클리드 호제법

| a와 b 의 최대공약수는 (a를 b로 나눈 나머지)와 b 의 최대공약수와 같다.

# a < b 유지
if(b>a) : a,b = b,a

while(b!=0):
  a=a%b
  a,b=b,a

• 큰 수를 작은 수로 나누고 나누어 떨어질 때까지 계속 반복

 

---

최소공배수

• math 내장 함수 사용하기

math.lcm(n, m)

• python 3.9부터 지원된다!

 

• 직접 구현하기

import math

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