[구현/수학] 백준 2702 초6 수학 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2702번: 초6 수학

 

 

 

2. 문제 풀이

 최대공약수와 최소공배수를 구하는 문제입니다. 초6 수학에서는 두 수를 나누어서 공약수를 일일이 구했지만, 그 방식을 코딩으로 구현하기에는 너무 부적합합니다.

 

2022.02.05 - [Algorithm] - [Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

[Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

 그대신, '유클리드 호제법'이라는 방법을 사용합니다. 유클리드 호제법의 설명과 코드는 위 글에서 보실 수 있습니다.

 

 

3. 코드

import sys
input = sys.stdin.readline

# 유클리드 호제법
def gcd(x, y):
    while y:
        if x > y:
            x, y = y, x
        y %= x
    return x

# 입력 및 출력
T = int(input())
for _ in range(T):
    a, b = map(int, input().split())
    gcd_num = gcd(a, b)
    print(a * b // gcd_num, gcd_num)

 유클리드 호제법으로 최대공약수를 구하고, [ 두수의 곱 / 최대공약수 ]로 최소공배수를 구합니다.