최대공약수와 최소공배수 (python)

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

문제 설명

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

 

제한 사항

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

---

code

# Lv.1
# 최대공약수와 최소공배수
def solution(n, m):
    answer = [0, 0]
    if n > m:
        answer[1] = get_least_common_multiple(m, n)
        answer[0] = get_greatest_common_measure(m, n)
    else:
        answer[1] = get_least_common_multiple(n, m)
        answer[0] = get_greatest_common_measure(n, m)
    return answer

def get_greatest_common_measure(num1, num2): # 최대 공약수 구하기
    answer = 0
    for i in range(1, num1 + 1):
        if num1 % i == 0 and num2 % i == 0:
            answer = i
    return answer
    
def get_least_common_multiple(num1, num2): # 최소 공배수 구하기
    i = num2
    while i % num1 != 0 or i % num2 != 0:
        i += num2
    return i

https://github.com/soaringwave/Python-algorithm-studying/blob/main/programmers/Lv.1/gcm_n_lcm.py

 

알고리즘

def get_greatest_common_measure(num1, num2): # 최대 공약수 구하기
    answer = 0
    for i in range(1, num1 + 1):
        if num1 % i == 0 and num2 % i == 0:
            answer = i
    return answer

 

최대 공약수를 구하는 함수다. num1은 num2 이하의 숫자이므로, 1부터 num1 + 1 중 num1과 num2에 나누어 떨어지는 수를 answer에 저장한다. 반복문을 모두 돌면 answer을 최대 공약수로 반환한다.

 

def get_least_common_multiple(num1, num2): # 최소 공배수 구하기
    i = num2
    while i % num1 != 0 or i % num2 != 0:
        i += num2
    return i

최소 공배수를 구하는 함수다. num1은 num2 이하의 숫자이므로, num2에서부터 num2의 배수 중 num1과 나누어 떨어지는 수가 발견되는 즉시 해당 수를 최소 공배수로 반환한다.

 

def solution(n, m):
    answer = [0, 0]
    if n > m:
        answer[1] = get_least_common_multiple(m, n)
        answer[0] = get_greatest_common_measure(m, n)
    else:
        answer[1] = get_least_common_multiple(n, m)
        answer[0] = get_greatest_common_measure(n, m)
    return answer

n, m 중 더 작은 수를 찾아 각각의 함수를 통해 최대 공약수와 최소 공배수를 구해 배열로 반환한다.