[BOJ 2609] 최대공약수와 최소공배수

[BOJ 2609] 최대공약수와 최소공배수 

 

1. 문제 : Link

말그대로 최대공약수와 최소공배수를 구하는 문제

 

2. 풀이

두 값을 작은값으로 나누면서 나머지가 둘 다 0이 되는 경우를 찾아서 배열에 넣어 최대공약수를 찾아준다.

최대공배수는 해당 값에 몫을 곱해주면 끝

 

3. 코드

유클리드 호제법이라는 쉬운 방법이 있지만 테스트할 때 떠오르지 않을 수도 있기 때문에..

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

maxx = max(a,b)
minn = min(a,b)

originmax = maxx
originmin = minn

divide = []

for i in range(minn, 1, -1):
    if maxx % i == 0 and minn % i == 0:
        maxx = maxx/i
        minn = minn/i
        divide.append(i)

if originmax == maxx:
    print(1, maxx * minn)
else:
    one = 1
    for d in divide:
        one *= d
    print(one, int(one * maxx * minn))