πŸ’» 개발/πŸ“ˆ μ•Œκ³ λ¦¬μ¦˜

μ΅œλŒ€κ³΅μ•½μˆ˜, μ΅œμ†Œκ³΅λ°°μˆ˜ κ΅¬ν•˜κΈ° (Feat. μœ ν΄λ¦¬λ“œ ν˜Έμ œλ²•)

EastShine_ 2022. 11. 27. 22:13

 

μœ ν΄λ¦¬λ“œ ν˜Έμ œλ²•μ„ μ΄μš©ν•œ μ΅œλŒ€κ³΅μ•½μˆ˜, μ΅œμ†Œκ³΅λ°°μˆ˜ μ•Œκ³ λ¦¬μ¦˜μ„ 파이썬 슀크립트둜 μ•Œμ•„λ³΄μž.

 

μ΅œλŒ€κ³΅μ•½μˆ˜(GCD)λž€?

- 두 μžμ—°μˆ˜μ˜ κ³΅ν†΅λœ μ•½μˆ˜ 쀑 κ°€μž₯ 큰 수

 

μ΅œμ†Œκ³΅λ°°μˆ˜(LCM)λž€?

- 두 μžμ—°μˆ˜μ˜ κ³΅ν†΅λœ 배수 쀑 κ°€μž₯ μž‘μ€ 수

μ΅œμ†Œκ³΅λ°°μˆ˜ = 두 μžμ—°μˆ˜μ˜ κ³± / μ΅œλŒ€κ³΅μ•½μˆ˜μœΌλ‘œ ꡬ할 수 μžˆλ‹€.

 

 

 

μœ ν΄λ¦¬λ“œ ν˜Έμ œλ²•(Euclidean algorithm)

  • 두 개의 μžμ—°μˆ˜μ˜ μ΅œλŒ€κ³΅μ•½μˆ˜λ₯Ό μ°ΎλŠ” 방법
  1. 큰 μˆ˜μ—μ„œ μž‘μ€ 수λ₯Ό λΉΌλ©΄ μ΅œλŒ€κ³΅μ•½μˆ˜λŠ” λ³€ν•˜μ§€ μ•ŠλŠ”λ‹€. λ”°λΌμ„œ λ‘˜ 쀑 더 큰 값을 λ°˜λ³΅ν•΄μ„œ λΉΌλ©΄ μ΅œλŒ€κ³΅μ•½μˆ˜κ°€ λœλ‹€. ( ex. 60, 36 ⇒ 60-36=24, 36-24=12, 24-12=12, 12-12=0. μ΅œλŒ€κ³΅μ•½μˆ˜ 12)
  2. λΉΌκΈ° λŒ€μ‹  λ‚˜λ¨Έμ§€λ₯Ό κ΅¬ν•˜λ‹€κ°€ 0이 될 λ•Œμ˜ μž‘μ€ 값이 μ΅œλŒ€κ³΅μ•½μˆ˜μ΄λ‹€. ( ex. 12, 28 ⇒ 12%28=12, 28%12=4, 12%4=0. μ΅œλŒ€κ³΅μ•½μˆ˜ 4)

 

 

파이썬 μ½”λ“œ

μ½”λ“œλ‘œ μ•„λž˜μ™€ 같이 μž‘μ„±ν•  수 μžˆλ‹€.

import sys

a, b = map(int, sys.stdin.readline().split())

# μ΅œλŒ€κ³΅μ•½μˆ˜
def gcd(a, b):
  tmp = 0
  while(b != 0):
    tmp = a % b
    a = b
    b = tmp
  return a

def lcm(a, b):
  return int(a * b / gcd(a,b))

print(gcd(a, b))
print(lcm(a, b))