2609: 최대공약수와 최소공배수-GCD 유클리드호제법

문제

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

입력

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

출력

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

예제 입력 1 복사

24 18

예제 출력 1 복사

6
72

 

 

유클리드 호제법은 a,b가 최대공약수가 있을때, a를 b로 나눈 나머지는 같은 최대공약수로 나누어 떨어져야 한다는 공식입니다. 최대공약수로 나누면 나누어떨어지니까요.

증명)

G가 최대공약수일때,

A= Bq +R, R =A-Bq이므로 R =Ga-Gbq로 정리할 수 있습니다. R= G(a-bq)이므로 R는 G로 나누어집니다.

• GCD(a, b) = GCD(b, a % b)
  (단, a > b)

그래서 유클리드 호제법의 핵심은 다음과 같은 성질을 이용하는 것입니다.

b보다 큰 값이 최대공약수가 될 수 없기 때문에 먼저 a%b를 해서 0이되면 b가 최대공약수이고 아니면

b%나머지를 할 수 있습니다.

이것도 아니면  나머지%나머지의 나머지 이런식으로 계산해갑니다.

일반적으로 1보다 큰 수로 나누어가기 때문에 브루트포스하게 b-1, b-2,...이런식으로 1씩 줄여가는 것보다 훨씬 빠릅니다.

 

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

while m!=0:
    tmp = n%m
    (n,m)= (m,tmp)
euclid = abs(n)

#최대공약수
print(euclid)
#최소공배수
print(leastMulti//euclid)