[PS] BOJ2609 최대공약수와 최소공배수 ( math ) with Python

 

@문제

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

 

@문제풀이

 

두 가지 풀이가 있다. 

 

1) 유클리드 호제법

2) 파이썬 math 라이브러리 사용

 

 

유클리드 호제법

 

자연수 A를 B로 나눌때 나머지 r이라면

유클리드 호제법은 A와B의 최대공약수는 B와 r의 최대공약수와 동일함을 의미한다. 

 

유클리드호제법 증명은 위 영상을 참고바란다.

그러면 B를 r로 나눌때 나머지 r2의 최대공약수도 A와B의 최대공약수와 동일하다.

그러면 r을 r2로 나눌때 나머지 r3의 최대공약수도 A와B의 최대공약수와 동일하다. 

.

.

.

그러면 rn-2를 rn-1로 나눌때 나머지 rn이 0이 되면 rn-1이 최대공약수가 된다.

rn-1로 나눌 때 0이 되는 가장 큰 수 이기 때문이다.

 

최소공배수는 A*B를 A,B의 최대공약수로 나누었을때 몫이 최소공배수이다. 

 

 

◎코드

 

유클리드 호제법

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

def GCD (x,y) :
  while(y) : 
    x,y = y,x%y
  return x

def LCM (x,y) :
  return (x*y)//GCD(x,y)

print(GCD(n,m))
print(LCM(n,m))

 

파이썬 math 라이브러리 

import math

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

print(math.gcd(n,m))
print(math.lcm(n,m))