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

문제

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

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6
72

---

기존의 초중고에서 배운 그 방법으로 코드를 짰다. 2로 나누고, 3으로 나누고 5로 나누고....

코드는 다음과 같다.

n1,n2=map(int,input().split())
GCD=1
LCM=1
n=2
while n<=n1 and n<=n2:
  if n1%n==0 and n2%n==0:
    GCD,n1,n2=GCD*n, n1//n, n2//n
  else :
    n+=1

LCM=(n1*n2)*GCD
print(GCD)
print(LCM)

 하지만 이 방법보다 더 좋은 방법이 있다.

그 유명한 유클리드 호제법으로 간단하게 풀 수 있다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

예를 들어

32, 14가 있다. 두 수 중 작은 수를 큰 수에 나누기 해준다. 32/14의 몫이 2, 나머지는 4가 남는다.

그러면 여기서 몫은 버리고 나눠졌던 14가 다시 큰 수로 나머지인 4가 작은 수로 나눠준다.

14, 4 ==> 14/4의 몫은 3 나머지는 2. 또 여기서 나눠졌던 4가 큰 수가 되고 나머지 2가 작은 수가 된다.

4, 2 ==> 4/2는 몫2, 나머지 0.

나머지가 0이 되었기에 나눠졌던 2가 최대공약수가 된다.

(32, 14) -> (14, 4) -> (4, 2) -> (2, 0) : 결과 최대공약수는 2가 된다. 몫의 2가 최대공약수가 아니고 나누었던 2가 최대공약수가 된다.

 

이렇게 계속 반복해서 0을 만드는 수가 최대공약수가 되는 것이 유클리드 호제법이다.

 

최소공배수는 간단하다. 두 수를 곱해준 후 최대공약수로 나눠주면 된다.

n1,n2=map(int,input().split())

def gcd(n1,n2):
  while n2>0:
    n1,n2=n2,n1%n2
  return n1

def lcm(n1,n2):
  return n1*n2//gcd(n1,n2)


if n1>n2:
  print(gcd(n1,n2))
  print(lcm(n1,n2))
else :
  print(gcd(n2,n1))
  print(lcm(n2,n1))

재귀적인 방법도 가능하다. 하지만 난 반복문이 더 좋다.ㅎ