코딩/공부

[Python] 백준 1934번 - 최소공배수

취미니스트 2023. 10. 10. 17:01
728x90
반응형

문제

https://www.acmicpc.net/problem/1934

 

유클리드 호제법을 이용하여 최소공배수를 구함

유클리드 호제법은 x와 y를 나누었을 때 나온 나머지 r에 대해 x, y의 최대공약수는 y, r의 최대공약수와 같다는 원리

최소공배수는 x * y를 최대공약수로 나눈 몫이 됨

이를 함수로 구현

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def lcm(x, y):
    return (x * y) // gcd(x, y)

정수 하나를 입력받고 입력한 숫자만큼 두 개의 정수를 입력받아 최소공배수를 구하여 출력

n = int(input())
for _ in range(n):
    a, b = list(map(int, input().split()))
    print(lcm(a, b))

전체 코드

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def lcm(x, y):
    return (x * y) // gcd(x, y)


n = int(input())
for _ in range(n):
    a, b = list(map(int, input().split()))
    print(lcm(a, b))
728x90
반응형