파이썬에서 최대공약수(gcd), 최소공배수(lcm) 구현 방법 정리

 

재귀로 구현

def gcd(x, y):
    if(y==0):
        return x
    else:
        return gcd(y,x%y)
        
def lcm(x,y):
	return (x*y)//gcd(x,y)

 

반복문으로 구현

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

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

 

람다함수로 구현

gcd = lambda a,b : b if not a%b else gcd(b, a%b)
lcm = lambda a,b : a*b//gcd(a,b)

 

파이썬 내장함수 이용

from math import gcd, lcm
x, y = map(int, input().split())
print(gcd(x,y))
print(lcm(x,y))

※주의※

lcm은 python 3.9 이상에서만 사용 가능. 

 

백준은 되는거 같은데 프로그래머스는 안됩니다.