📃 문제 설명

최대공약수와 최소공배수

[문제 출처 : 프로그래머스]

👨‍💻 해결 방법

나는 단순하게
n과 m의 최대공약수를 구할 때
1부터 n,m 중 더 큰 수까지 반복문을 돌면서
둘 다 나누어 떨어지는 수 중 가장 큰 수를 구했다.

그리고 최소공배수를 구할 때는
n,m중 더 큰 수를 기준으로 *2,3,4....
이렇게 곱해나가면서 나머지 수로 나누어 떨어지는 가장 작은 수를 최소공배수로 했다.

그런데
최대공약수를 구할 때 유클리드 호제법을 이용하면 더 간단하게 풀 수 있었다.

유클리드 호제법

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

자세한 것은 유클리드 호제법 정리

유클리드 호제법에 대해 정리할 수 있는 좋은 날이었다.

👨‍💻 소스 코드

def solution(n, m):
    answer = [0]

    temp = 1
    while temp <= max(n, m):
        if n % temp == 0 and m % temp == 0:
            answer[0] = temp
        temp += 1

    temp = m
    while temp % n != 0:
        temp += m
    answer.append(temp)

    return answer

유클리드 호제법 이용

def solution(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