코딩테스트/Python
GCD(Great Common Divisior), LCM(Least Common Multiple)
swwho
2023. 3. 24. 16:43
728x90
반응형
1. for문 활용
a, b = 12, 10
# GCD - 최대공약수
for i in range(min(a,b), 0, -1):
if a % i == 0 and b % i == 0:
gcd = i
break
# LCM - 최소공배수
for i in range(a*b, 0, -1):
if i % a == 0 and i % b == 0:
lcm = i
break
2. 유클리드 호제법 활용
a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다
위 정의에 따라, r가 0일때의가 최대공약수가 된다. 또한, 두 수의 곱을 최대공약수로 나눈 값이 최소공배수가 된다.
# GCD - 최대공약수
def GCD(a, b):
while b > 0:
a, b = a // b, a % b
return a
# LCM - 최소공배수
def LCM(a, b):
return (a*b) // GCD(a, b)
3. Math 라이브리러리 활용
import math
a,b = 12, 10
gcd = math.gcd(a, b)
lcm = math.lcm(a, b)