Python - 최대공약수와 최소공배수

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한사항

두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1

위의 설명과 같습니다.

입출력 예 #2

자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

문제 풀이

def GCD(n, m):
	while m > 0:
    	n, m = m, n % m
    return n

def solution(n, m):
	result = [GCD(n, m), (n * m) // GCD(n, m)]
    return result

코드 설명

def GCD(n, m):
	while m > 0:
    	n, m = m, n % m
    return n

• 최대공약수를 구하는 함수를 따로 만들어 진행하였다.

최대공약수를 구하는 함수에서 유클리드 호제법이 사용되었다.

• 유클리드 호제법
  2개의 자연수 x, y에 대해서 x를 y로 나누 나머지를 r이라 할 때, x와 y의 최대공약수는 y와 r의 최대공약수와 같다.
  따라서 y를 r로 나눈 나머지를 r'라 하고 r'을 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 x와 y의 최대공약수이다.

def solution(n, m):
	result = [GCD(n, m), (n * m) // GCD((n, m)]
    return result

• 최소공배수는 두 수의 공통의 배수중 가장 작은 수로 두 수의 곱을 최대공약수로 나눈 몫이 최소공배수가 된다.
  따라서

result = [GCD(n, m), (n * m) // GCD((n, m)]

위 코드에서 result[0]에는 최대공약수, result[1]에는 최소공배수가 오게 된다.