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

문제 링크

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

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

풀이 

- 처음엔 for 문 사용해서 작성했는데 시간 초과 

#시간 초과 
n, m = map(int,input().split())

for i in range(min(n,m), 0, -1):
  if n % i == 0 and m % i == 0 :
    print(i)
    break

for j in range(max(n,m), n*m+1):
  if j % n == 0 and j % m == 0 :
    print(j)
    break

- 유클리드 호제법 사용 

: x, y의 최대공약수는 y, r의 최대 공약수와 같다는 원리는 이용

: 이때 r = x % y 

- 최대공약수 : x%y는 0일 때까지  x에는 y를 대입하고 y에는 (x%y) 값을 대입. x가 y로 나누어 떨어질 때의 y값이 x,y의 최대 공약수 

- 최소공배수 : x*y를 최대 공약수로 나눈 몫 

n, m = map(int,input().split())

#최대 공약수 
def gcd(x,y):
  while(y):
    x, y = y, x%y 
  return x

print(gcd(n,m))

# 최소 공배수
def lcm(x,y):
  return (x*y) // gcd(x,y)

print(lcm(n,m))

소수 구하는 방법처럼 알고 있으면 좋을 것 같다 .

 

- 찾아보니 파이썬의 내장 함수를 사용해도 된다. 

- replit 에서는 module 'math' has no attribute 'lcm' 라는 에러가 떴는데 이는 파이썬의 버전이 3.9 이하 일 경우 발생하는 에러라고 한다. 

import math 

n, m = map(int,input().split())

print(math.gcd(n,m))

print(math.lcm(n,m))