TIL - 프로그래밍/Python 알고리즘
Python 최대공약수 / 최소공배수
chaemj97
2022. 9. 22. 22:59
728x90
- import math
import math
a,b = map(int,input().split())
# 최대공약수 (Greatest Common Divisor)
print(math.gcd(a,b))
# 최소공배수 (Lowest Common Multiple)
print(math.lcm(a,b))
- 유클리드 호제법
- 시간복잡도 O(logN)
- 2개의 자연수 a,b(a>b)에 대해서 a를 b로 나눈 나머지를 r0이라 하면
- a와 b의 최대공약수 == b와 r0의 최대공약수
- 위 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 최대공약수
def gcd(a,b):
while b>0:
a,b = b, a%b
return a
def lcm(a,b):
return (a*b)//gcd(a,b)
728x90
반응형