프로그래머스 / 코딩 테스트 / 최대공약수와 최소공배수

문제 설명

 

 

문제 해결

 

math 모듈을 import 하여 간단하게 풀 수 있다.

 

import math

def solve(n,m):
    return [math.gcd(n,m), n * m / math.gcd(n,m)]

def solution(n, m):
    answer = solve(n,m)
    return answer

 

두 수의 최대공약수를 구하는 방법이 무엇이 있을까 찾아봤고 유클리드 호제법을 발견했다.

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

최대 공약수를 구하는 알고리즘을 찾아 직접 구현하여 풀어봤다.

 

def gcd(n,m):
    if n < m:
        t = m
        m = n
        n = t
    t = m
    while n % m != 0:
        t = n % m
        n = m
        m = t
    return t

def solve(n,m):
    return [gcd(n,m), n * m / gcd(n,m)]

def solution(n, m):
    answer = solve(n,m)
    return answer