[Python] 최대공약수와 최소공배수

 

코딩테스트 연습 - 최대공약수와 최소공배수

유클리드 호제법을 사용하여 최대공약수를 구하고 최소공배수는 두 수의 곱에 최대공약수를 나눈 값이라는 것을 이용하여 문제를 풀었다.

유클리드 호제법의 설명은 다음 링크에 정리했다.

유클리드 호제

def solution(n, m):
    def gcd(n,m):
        while m:
            n, m = m, n % m
        return n
    def lcm(n,m):
        return (n*m) // gcd(n,m)
    
    answer = [gcd(n,m), lcm(n,m)]
    return answer

파이썬의 내장함수를 사용하여 풀이할 수도 있다.

from math import gcd
def solution(n, m):
	return [gcd(n,m), (n*m)//gcd(n,m)]