2021.09.28 - [재귀 호출] 최대공약수 구하기 / 피보나치 수열
[재귀 호출] 최대공약수 구하기 / 피보나치 수열
최대공약수 최대공약수 Greatest Common Disiver, GCD 두 개 이상의 정수의 공통 약수 중 가장 큰 값 방법 1. 정수 중 작은 값부터 1씩 감소시키면서 약수인 값을 찾는다. 2. 유클리드 알고리즘 a와 b의 최
passwd.tistory.com
위 글에서 재귀 호출을 이용해 최대공약수를 계산하는 알고리즘에 대해 다루었다.
최대공약수를 구할 수 있다면 최소공배수도 자연스럽게 구할 수 있다. 두 수의 곱을 최대공약수로 나눈 값이 최소공배수이기 때문이다.
$$ gcd(a,b)*lcm(a,b)=a*b $$
그렇다면 Python으로 최대공배수/최대공약수를 계산할 때 반드시 알고리즘을 구현해 계산해야할까?
그건 아니다. 내장 모듈인 math에서 기능을 제공하기 때문이다.
gcd()
매개변수로 전달받은 수의 최소공배수를 계산한다.
코드
import math
a = 3
b = 12
print(math.gcd(a, b))
실행 결과
lcm()
매개변수로 전달받은 수의 최대공약수를 계산한다.
코드
import math
a = 3
b = 12
print(math.lcm(a, b))
print(a * b // math.gcd(a, b))
실행 결과
