Python_최대공약수와 최소공배수

---

<문제>

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

---

<생각 흐름 상 풀이>

def solution(n, m):
    for i in range(2, 1000000):
        for j in range(2, 1000000):
            if m%j == 0 and n%i == 0:
                if i == j:
                    if i == n or j == m:
                        return [i, int(i*(m/i)*(n/i))]
                    else:
                        return [i,int((m/i)*(n/i))]
                    break  
            if n%m == 0:
                return [m, n]
            break
        if m%n == 0:
            return [n, m]
        break
    if (m%j != 0 and n%i !=0) and (n%m != 0) and (m%n != 0):
        return [1, n*m]
    elif (m%j == 0 and n%i !=0) and (n%m != 0) and (m%n != 0):
        return [1, n*m]
    elif (m%j!= 0 and n%i ==0) and (n%m != 0) and (m%n != 0):
        return [1, n*m]
        # 안풀림. 때에 따라 다르게 결과 도출

<최종 풀이>

def solution(n, m): 
    min_i = 0
    max_i = 0
    for i in range(min(n,m),0,-1): # 최대공약수 구하기
        if n%i == 0 and m%i == 0:
            min_i = i
            break
        
    for i in range(max(n,m), (n*m)+1): # 최소공배수 구하기
        if i%n == 0 and i%m == 0:
            max_i = i
            break
            
    return [min_i, max_i]

---

<다른 풀이>

방법 1.

def gcdlcm(a, b):
    c, d = max(a, b), min(a, b)
    t = 1
    while t > 0:
        t = c % d
        c, d = d, t
    answer = [c, int(a*b/c)]

    return answer

방법 2.

def solution(n, m):
    nlist = []
    mlist = []
    for i in range(1, n+1):
        if n%i == 0:
            nlist.append(i)
    for i in range(1, m+1):
        if m%i == 0:
            mlist.append(i)
    maxi=[]
    for i in nlist:
        if i in mlist:
            maxi.append(i)
    maximum = max(maxi)

    minimum = int(maximum * (n/maximum) * (m/maximum))

    answer = [maximum, minimum]
    return answer

---

<개념>

방법 1: Euclidean algorithm 도입

출처 : https://j1w2k3.tistory.com/1173

---