최대공약수와 최소공배수

프로그래머스

 

 

문제

---

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

 

 

 

 

코드

---

def solution(n, m):
    answer = []
    for i in range(min(n, m), 0, -1):
        if (n%i==0) & (m%i==0):
            answer.append(i)
            break
    for j in range(max(n, m), 1000000):
        if (j%n==0) & (j%m==0):
            answer.append(j)
            break

    return answer

• 작은 수부터 -1씩하며 n,m의 약수를 찾음
• 큰 수부터 +1씩하며 n,m의 배수를 찾음

 

 

노트

---

def solution(n, m):
    gcd = lambda a,b : b if not a%b else gcd(b, a%b)  # 최대공약수 찾는 함수
    lcm = lambda a,b : a*b//gcd(a,b)  # 최소공배수 찾는 함수
    return [gcd(n, m), lcm(n, m)]

• 재귀함수. 자기 자신을 호출!
•  A*B = gcd(A,B) * lcm(A,B) 이용

 

 

참조

---

https://school.programmers.co.kr/learn/courses/30/lessons/12940/solution_groups?language=python3

프로그래머스