두 자연수 A, B 가 주어졌을때 두 수의 최대 공약수와 최대 공배수를 구하는 방법을 알아보겠습니다.

공약수로 나누기

이 방법은 두 수가 더 이상 나누어지지 않을때까지(서로소가 될때까지) 공약수로 나누고 
해당 공약수들을 모두 곱해주면 최대 공약수를 구할 수 있습니다. 

최대 공배수는 최대 공약수 값에 서로소가된 값을 곱해줍니다.

일반적인 공약수를 이용한 최대 공약수, 최대 공배수를 구하는 방식을 구현한 코드입니다.

def solution(a, b):

    gcd = 1

    x = 2
    while x < (max(a, b) // 2)+1:

        if a % x or b % x:
            x += 1
            continue

        a //= x
        b //= x

        gcd *= x

    return [gcd, gcd * a * b] # [최대공약수, 최소공배수]

유클리드 호제법 사용하기

위 방식은 간단하게 구현할 수 있는 방법이지만 그만큼 효율면에서는 불리합니다.

그렇다면 알고리즘의 효율을 더 올리고 싶다면 어떻게 하면 좋을까요?

그 해답은 바로 유클리드 호제법 입니다!

유클리드 호제법을 코드로 구현해보겠습니다.

def solution2(a, b):

    ab = a*b

    while b != 0:
        r = a % b
        a, b = b, r

    return [a, int(ab/a)]
    
if __name__ == '__main__':

	print(solution2(2, 5)) # [1, 10]

유클리드 호제법 알고리즘

1. 입력으로 두 수 a, b (a, b > 0)가 전달된다
2. a를 b로 나눈 나머지 값을 r에 할당한다.
3. 나머지 r은 a, a를 나눈값 b는 a에 각각 할당한다.  
4. a가 b로 나누어 떨어지지 않으면 2~3번을 반복한다. ( 이전에 나눈값 / 나머지의 나눗셈이 반복 )
5. 나머지 값 r이 0이면 ( a가 b에 나누어 떨어지면) b가 최대공약수 값이다.

유클리드 호제법 알고리즘

핵심은 값이 나누어떨어질때까지 직전에 나눈값과 나머지를 계속 나눠주는 것이다.

마지막으로 공약수로 나눈 방식과 유클리드 호제법의 속도차이를 보겠습니다.

solution(49278, 4028928)
solution2(49278, 4028928)

# WorkingTime[solution]: 0.00342798 sec
# WorkingTime[solution2]: 0.00000596 sec

감사합니다.