[프로그래머스] : 최대공약수와 최소공배수 파이썬 풀이

---

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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(a, b):
    if a<b:
        (a, b) = (b, a)
    while b != 0:
        (a, b) = (b, a % b)
    return a

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

print(solution(3, 12))

유클리드 호제법을 사용한 최대공약수와 최소공배수를 구하는 코드이다.

유클리드 호제법은 두 수가 서로 상대방 수를 나눠 결국 원하는 수를 얻어내는 알고리즘이다.

def gcd(a, b):
    if a<b:
        (a, b) = (b, a)
    while b != 0:
        (a, b) = (b, a % b)
    return a

우선 a에 큰 수가 오게 끔 if문을 통해 만들어주고 a와 b의 최대공약수는 b와 a를 b로 나눈 나머지와의 최대공약수와 같기 때문에 0이 될 때 까지 반복해 준다. 이때, b가 0일떄 a의 값이 a,b의 최대공약수가 된다.

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

최대공약수는 gcd 함수를 통해 구해졌고 최소공배수를 m에 넣어줘야 하는데 최소 공배수는 a,b의 곱을 최대공약수로 나눈 값이 되므로 a=n, b=m을 생각해서 그대로 넣어주어 완성시켰다.