코딩테스트/알고리즘
[Python] 프로그래머스 - 최대공약수와 최소공배수
브라보서
2021. 8. 8. 18:38
- 최대공약수 -> Greatest Common Divider
- 최소공배수 -> Largest Common Divider
def gcd(a, b):
if a > b :
min = b
else:
min = a
for i in range(min+1, 0, -1):
if a % i == 0 and b % i == 0:
gcd = i
break
return gcd
def lcm(a, b):
if a > b :
max = a
else:
max = b
for i in range(max, a*b+1):
if i % a == 0 and i % b == 0:
lcm = i
break
return lcm
def solution(a, b):
return [gcd(a,b), lcm(a,b)]
- 유클리드 호재법
def gcd(X, Y):
while Y > 0:
X, Y = Y, X%Y
return X
def lcm(X, Y):
return X*Y // gcd(X, Y)
def solution(a, b):
return [gcd(a,b), lcm(a,b)]