문제

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

www.acmicpc.net/problem/2609

  • 입력

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

  • 출력

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

과정

그냥 loop 돌려서 풀려다가 정석(?)으로 풀어보자 싶어서 두 수를 소인수분해 한 뒤에 교집합과 합집합을 구해서 풀었다. 코드의 길이는 길지만 내용은 별 거 없다.

a, b = map(int, input().split())

A = [1]
B = [1]

i = 2
while i <= a:
    if a%i == 0:
        A.append(i)
        a = a//i
    else:
        i += 1

i = 2
while i <= b:
    if b%i == 0:
        B.append(i)
        b = b//i
    else:
        i += 1

i = j = 1
res1 = res2 = 1
while i < len(A) and j < len(B):
    if A[i] == B[j]:
        res1 *= A[i]
        res2 *= A[i]
        i += 1
        j += 1
    elif A[i] > B[j]:
        res2 *= B[j]
        j += 1
    else:
        res2 *= A[i]
        i += 1

while i < len(A):
    res2 *= A[i]
    i += 1
while j < len(B):
    res2 *= B[j]
    j += 1

print(res1)
print(res2)

최종 코드

아니 근데 훨씬 간단하게 푸는 방법이 있을 것 같은데.. 하고 검색해보니 유클리드 호제법이라는 게 있더라. 이거 나만 몰랐나?

유클리드 호제법이란 a와 b의 최대공약수는 b와 a % b의 최대공약수와 같다는 것이다.

최소공배수는 더 쉽다. a * b를 최대공약수로 나누면 된다.

a, b = map(int, input().split())

# 최대공약수
def gcd(a, b):
    tmp = a
    while b>0:
        tmp = a
        a = b
        b = tmp % b
    return a

# 최소공배수
def lcm(a, b):
    return (a * b) // gcd(a, b)

print(gcd(a, b))
print(lcm(a, b))

이렇게 훨씬 간단하게 구현할 수 있다.

Enhanced

뭐야 찾아보니 math에 최대공약수를 구하는 gcd이라는 함수가 내장되어 있었다. 이것도 나만 몰랐나? 내장함수를 사용하면 너무 쉽잖아?

from math import gcd
a, b = map(int,input().split())
print(gcd(a, b))
print(a * b // gcd(a, b))

참고 사이트