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

⛏ 문제 파악

• 말 그대로 최대공약수와 최대공배수를 구하는 문제
• 최대공약수(GCD / Greatest Common Divisor) : 두 수의 공통된 약수인 정수로, 약수 중에 제일 큰 수
• 최소공배수(LCM / Least Common Multiple) : 양의 공배수 가운데 가장 작은 수
• 유클리드 호제법으로 문제를 풀면 된다.
•  유클리드 호제법
  • 유클리드 호제법은 2개의 자연수 또는 정수의 최대공약수를 구하는 알고리즘의 하나로, 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
  • 2개의 자연수(또는 정수) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수(gcd)는 b와 r의 최대공약수와 같다.
  • 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 👉🏻  답안

X, Y = map(int, input().split())

def gcd(a, b): # 최대 공약수 구하는 함수
  while b != 0: # b = 0이 될 때까지 반복
    r = a % b # a를 b로 나눈 나머지를 r에 대입
    a = b # b값을 a로
    b = r # r값을 b로 넣어준 뒤 반복
  return a # b가 0이면 a값을 리턴

def lcm(a, b): #최소공배수 함수
  lcm = (a * b) // gcd(a, b) # a * b 값에 a, b의 최대 공약수를 나누면 최소공배수
  return lcm 

print(gcd(X,Y))
print(lcm(X,Y))

📑  간단한 설명

• 유클리드 호제법으로 최대공약수를 구하면
  • a를 b로 나눈 나머지를 r
  • a와 b의 최대공약수는 b와 r의 최대 공약수
  • 즉 a와 b의 최대공약수는 b와 a%b의 최대공약수이다.
• 최소공배수를 구하는 것은
  • 최대 공약수가 G라면
  • a  = G * x
  • b = G * y
  • 최대공약수가 G이기에, x,y는 서로소이다.
  • 그러면 최소 공배수는 a * b / G가 된다.
• 물론 이렇게 안해도 파이썬에서 제공하는 강력한 math가 있다..

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