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

문제

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

입력

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

출력

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

---

풀이

#파이썬에는 count라는 좋은 내장함수가 있음

n,m=map(int,input().split())
def devide(n): #인수분해
    devided=[]
    factor=2 # 인수는 2부터 시작
    while n!=1:
        if(n%factor==0):
            devided.append(factor)
            n=n//factor
        else:
            factor+=1
    return devided

def findAnswer(n,m): # answer1은 최소공배수, answer2는 최대공배수 반환
    answer1=1
    answer2=1
    factorN=devide(n)
    factorM=devide(m)
    
    factors=list(set(factorN)|set(factorM))#공통인수 - N 과 M합집합
    for factor in factors:
        answer1=answer1*(factor**(min(factorN.count(factor),factorM.count(factor))))
        answer2=answer2*(factor**(max(factorN.count(factor),factorM.count(factor))))
    return [answer1,answer2]

print(findAnswer(n,m)[0])
print(findAnswer(n,m)[1])

나중에도 써먹기 좋을 함수같아서, 특정 수의 인수를 구하는 devide 함수를 만든다.

이후 합집합을 이용하여, 두 수의 공통인수를 보여주는 factors라는 list를 만든다.

보통 최소 공배수, 최대 공배수를 구할 때는 소인수분해를 하게 되는데
36, 12의 인수는 각각 [1,2,2,3,3][1,2,2,3]으로 만들어진다.
이 때 최소공배수는 2를 2번, 3을 2번 곱해야한다. (두 인수중 나온 횟수가 더 많은 것을 택해 곱해줘야한다)

반대로 최대공약수는 두 인수 중 개수가 나온 횟수가 더 적은 것을 택해 곱해줘야한다. 즉, 2 2번, 3 1번 곱한 12가 나온다.

즉, 최소공배수는 두 인수중 나온 횟수 중 더 많은 값을 택해 곱하고,
최대공약수는 두 인수 중 나온 횟수 중 더 적은 값을 택해 곱한다.