[코테] GCD, LCM (최대공약수, 최소공배수)

오늘은 GCD, LCM를 구하는 방법을 알아보자

GCD : Greatest Common Divisor
LCM:Least Common Multiple

import math
def lcm(a, b):
    return a * b / math.gcd(a, b)

def solution(n, m):
    answer = []
    answer.append(math.gcd(n,m));
    answer.append(lcm(n,m));
    return answer

파이썬에서 gcd는 math 라이브러리를 호출해서 그냥 쓰면 된다.
but lcm은 3.9 이상부터 지원하기 때문에 a*b/gcd 로 나눠서 구해주자!

유클리드 호제법

그래도.. 정석적으로 구하는 방법을 알아보자
GCD 구하기
1. a,b 가 주어졌을 때 2부터 두 자연수 중 작은 자연수 까지 모두 나누어보면서 구하기
2. 유클리드 호제법

• a를 b로 나눈 나머지를 r이라 하면(a>b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다
• 따라서 A%b가 0이되는 순간 B의 값이 최대공약수이다!

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a