[백준/Python] 1934번 최소공배수 문제

■ 1934번 최소공배수 문제

 

출처: 백준 1934번 최소공배수 문제

 

 

■ 코드 풀이

 

두 숫자의 최소 공배수는 두 숫자를 곱한 다음 최대 공약수로 나눈 몫입니다. 따라서 최소 공배수를 구하려면 먼저 최대 공약수를 구해야 합니다. 최대 공약수는 유클리드 호제법이라는 알고리즘으로 쉽게 구할 수 있습니다.

유클리드 호제법을 코드로 구현하면 아래 코드에서 while문인데요. a가 b보다 크거나 같은 수일 때, a를 b로 나눈 나머지를 a에 넣고 b를 a로 나눈 나머지를 b에 넣습니다. 그렇게 (a, b) 값을 b가 0이 될 때까지 갱신하면 a에는 a와 b의 최대 공약수가 들어가게 됩니다. 상세한 내용과 증명은 아래 위키백과의 링크를 참고해 주세요.

 

T = int(input())

for _ in range(T):
    numbers = list(map(int, input().split()))
    numbers.sort()
    
    if numbers[0] == 1:
        print(numbers[1])
        continue
    
    numbers.sort(reverse=True)
    a,b = numbers[0], numbers[1]
    
    # 유클리드 호제법으로 최대 공약수 구하기
    while b != 0:
        a = a%b
        a,b = b,a
        
    # 두 숫자의 곱 // 최대 공약수 = 최소 공배수
    print((numbers[0] * numbers[1]) // a)

 

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

유클리드 호제법 - 위키백과, 우리 모두의 백과사전