[백준/python] 2609번 : 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

정답

n, m = map(int, input().split())

div = 0
for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        if m % (n / i) == 0:
            div = n // i
            break
        elif m % i == 0:
            if div < i:
                div = i

mul = n
while mul % m != 0:
    mul += n

print(div)
print(mul)

---

div = 0
for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        if m % (n / i) == 0:
            div = n // i
            break
        elif m % i == 0:
            if div < i:
                div = i

최대공약수를 구하는 방법이다.

두 수 n, m 중 하나 n을 1부터 n의 제곱근까지 나누었을 때 나머지가 0이라는 뜻은

n이 i와 n/i를 약수로 가지고 있다는 의미이다.

약수는 가장 작은 수와 가장 큰 수가 짝을 이루기 때문에 n/i가 약수 중 가장 큰 수가 된다.

나머지 수 m을 n/i로 나누었을 때 나머지가 0이라면 m도 n/i를 약수로 가지고 있다는 의미이므로

div에 n/i의 몫을 저장한다. 이 때 결과는 정수로 출력되어야하므로 n//i를 저장한다.

n/i가 제일 큰 수 이므로 더 이상 큰 공약수는 없기 때문에 break를 통해 반복문을 빠져나간다.

mul = n
while mul % m != 0:
    mul += n

최소공배수 구하는 방법이다.

우선 mul에 두 수 중 하나 n을 넣는다.

mul을 m으로 나눴을 때 나머지가 0이라면 m의 배수라는 뜻이므로

mul을 m으로 나눈 나머지가 0이 될 때까지 mul에 n을 더하여 mul 값을 n의 배수로 유지한다.

 

import math

a, b = map(int, input().split())
print(math.gcd(a, b))
print(math.lcm(a, b))

사실 두 방법 외에 math 내장함수를 이용하여 바로 구할 수 있다.

math.gcd()는 최대공약수를 의미하고 math.lcm()은 최소공배수를 의미한다.