[Daily 코테] 백준 2609번: 최대공약수와 최소공배수

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

First Try

"""
최대공약수 : 교집합
최소공배수 : 합집합
"""
def get_factors(x: int) -> list:
"""
입력받은 x의 약수를 반환한다.
"""
  factors = []
  n = 2
  while (True):
    if x == 1:
      break
    if x % n == 0:
      factors.append(n)
      x = x / n
    else:
      n += 1
  return factors

def get_gcn(a, b: list):
"""
두 수의 약수 리스트를 각각 입력받고, 최대공약수를 출력한다.
"""
  inter = set(a)&set(b) #공약수이므로 두 수에 공통으로 포함된 약수를 교집합을 활용하여 구한다.
  result = 1
  for n in inter:
    result *= n**min(a.count(n),b.count(n)) 
  return result

def get_lcm(a ,b):
"""
두 수의 약수 리스트를 각각 입력받고, 최소공배수를 출력한다.
"""
  union = set(a)|set(b) # 공배수이므로 두 수의 약수들 중 하나 이상 포함하는 모든 약수들을
                    # 합집합을 활용하여 구한다.
  result = 1
  for n in union:
    result *= n**max(a.count(n),b.count(n))
  return result

num1, num2 = map(int, input().split())
print(get_gcn(get_factors(num1),get_factors(num2)))
print(get_lcm(get_factors(num1),get_factors(num2)))