분류 : 수학, 정수론, 유클리드 호제법

1. 문제

---

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

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

2. 아이디어

---

• 유클리드 호제법
  mine

  1. 최대공약수 구하기 (gcd 사용)
  2. 최소공배수 구하기 (두 수의 곱을 gcd로 나눔)
     출처 : https://velog.io/@onejh96__/CodeUp1092
     someone
  3. 최대공약수 구하기 (gcd 사용)
  4. 최소공배수 구하기 (lcm 사용)
     출처 : https://www.acmicpc.net/source/25380750

3. 코드

---

mine

from math import gcd

a, b = map(int, input().split())
gcdNum = gcd(a,b)
lcmNum = a*b//(gcdNum)
print(gcdNum)
print(lcmNum)

출처 : https://github.com/Gitgorithm/wogus0333_Github/blob/main/BOJ/BOJ_2609.py
someone

import math

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

4. 개선 사항

---

코드가 간결해졌고 68ms -> 60ms로 8ms 시간 감축 효과가 있다. gcd는 알고 lcm은 모르는 나란.. 남자