파이썬 - 여러 수의 최소공배수 구하기

 저번에 유클리드 호제법으로 최대공약수를 구했지!

 이번에는 최대공약수를 가지고 두 수의 최소공배수부터 여러 수의 최소공배수를 구해볼거야!

 아, '최소공배수 最小公倍數'는 LCM이라고도 하는데 Lowest Common Multiple의 약자로 쓰여.

 

 최소공배수를 구하는 방법 또한 여러가지가 있겠지만 우리는 두 수의 최대공약수를 구하는 방법을 알아냈으니까 최대공약수를 이용해서 구해볼거야.

 

 먼저 두 수의 최소공배수를 알아볼까? 최대공약수만 알고 있으면 넘나리 쉽게 구할 수 있어! 두 수를 곱해서 최대공약수로 나누면 그게 최소공배수지! 엄청 간단하지?

 

A와 B의 최소공배수 = A X B ÷ A와 B의 최대공약수

 

 그럼 여러 수의 최소공배수는 어떻게 구할 수 있을까?

 

 여러 수의 최대공약수를 구할 때 처럼, 일단 아무 두 숫자를 골라 잡아서 최소공배수를 구한 다음 나머지 다른 숫자랑 또 최소공배수를 구하면! 그게 바로 세 수의 최소공배수가 되는거야!

 

A, B, C의 최소공배수 ① A와 B의 최소공배수를 구한다. ② ①과 C의 최소공배수를 구하면! 그게 바로 A, B, C의 최소공배수!

 

 최대공약수만 구할 수 있으면 최소공배수는 껌이지? 그럼 이제 저번에 다뤘던 최대공약수를 구하는 알고리즘을 이용해 최소공배수를 구해볼까?!

 대신 이번에도 리스트 arr에 있는 여러 수의 최소공배수를 차례대로 구해 나갈건데.. 그러기 위해서 임의의 초항을 만들어 줄거야. 임의의 초항은 최대공약수 때와 마찬가지로 리스트 arr에 있는 첫 번째 항목(0번 방)으로 하면 되겠지? 왜냐면 최소공배수 또한 최대공약수와 마찬가지로 똑 같은 숫자 두 개에 대해 구하려고 하면, 자신 숫자가 그대로 나오기 때문이지! 3과 3의 최소공배수는 3이 되는 것 처럼 말야!

 

 최대공약수 코드와 비슷하게 만들어 지겠지만 이번에는 최대공약수를 이용해 최대공배수를 구해야 하기 때문에 변수의 흐름을 따라가는게 쉽지 않을거야. 그래서 변수의 값이 어떻게 달라지는 지 볼 수 있도록 출력을 해가면서 살펴 볼 수 있도록 코드를 만들었어!

 

arr = list(map(int, input().rstrip().split())) #공백문자로 구분하여 리스트 입력받기
 
def gcd_two_numbers(a, b): #gcd_two_numbers라는 이름의 함수와 매개변수 a, b 정의하기
    while b != 0 : #b가 0이 아닌 동안 반복
        a, b = b, a%b #a에 b를, b에 a와 b를 나눈 나머지를 교환하여 저장(스왑)
    return a #반환되는 a가 두 수의 최대공약수
 
GCDarr = arr[0] #arr 리스트의 첫 번째 항목(0번 방)을 GCDarr에 저장
LCMarr = arr[0] #arr 리스트의 첫 번째 항목(0번 방)을 LCMarr에 저장
for i in range(len(arr)): #i가 0부터 리스트 arr의 길이만큼 반복
    print(LCMarr, ",", arr[i], "의 최대공약수 = ", end="") #최대공약수 출력
    GCDarr = gcd_two_numbers(LCMarr, arr[i]) # GCDarr에 LCMarr과 arr[i]의 최대공약수를 저장
    print(GCDarr) #GCDarr 출력
 
    print(LCMarr, ",", arr[i], "의 최소공배수 = ", end="") #최소공배수 출력
    LCMarr = LCMarr * arr[i] // GCDarr #LCMarr에 LCMarr과 arr[i]의 최소공배수를 저장
    print(LCMarr) #LCMarr 출력

 

 주의할 점은, 이미 구해진 최대공약수와 arr[i]의 최대공약수를 구하는 것이 아니라 최소공배수와 arr[i]의 최대공약수를 구해야 한다는 점이야! 우리의 목적은 최대공약수가 아니라 최대공약수를 이용해 최소공배수를 구하는 것이기 때문이지!

 

 이 알고리즘을 이용하면 아무리 많은 수가 있다고 해도 최소공배수를 쉽게 구할 수 있어! 하지만 이 코드가 세상에서 제일 좋은 코드라고 할 수는 없으니 친구들도 자신만의 알고리즘을 만들어 보는 건 어떨까?

 

 친구들~ 안뇽!