내 풀이
def gcd(n,m):
mod = m % n
if mod != 0:
m, n = n, mod
return gcd(n, m)
else:
return n
def solution(n,m):
return [gcd(n,m),int(m*n/gcd(n,m))]+++
유클리드 호제법
- 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘
호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
+++
GCD, LCM (최대공약수, 최소공배수)
* GCD(Great Common Divisor)
A,B가 주어지면
A,B를 서로 나누어 0이 될 때까지 나머지를 구한다.
GCD(B,A%B)
if A%B = 0, GCD=B
else GCD(B,A%B)
* LCM(Least Common Multiple)
(A*B)/GCD
Engineer