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

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

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

 

풀이

import sys
a,b = map(int,sys.stdin.readline().split())
c=a%b
d=a*b
while b!=0:
    if (a%b)==0:
        c=b
        break
    c=a%b
    a=b
    b=c
    
print(c) #유클리드 호제법
print(int(d/c)) #최대공약수 * 최소공배수 = a*b와 같다.

 

단순한 방법으로는 범위가 넓고 구할 수 없기에, 유클리드 호제법을 사용한다.

 

유클리드 호제법이란 복잡해 보이지만 쉽게 말하면 a를 b로 나눈 나머지가 c이라면,

C가 0일때까지 b를 a에 집어 넣고, c를 b에 집어넣으며 갱신을 계속해 나갔을 때 마지막 b의 숫자가 최대공약수가 된다는 원리이다.

 

예를 들어 27 / 6 이라면,

[1] a= 27, b=6, a / b +3 이 성립되므로 27 % 6 = 3

[2] 6 / 3 = 0 이므로 3이 27과 6의 최대공약수가 된다는 것.

 

또 다른 수학적 원리를 이용해서 최소공배수도 구할 수 있는데, 최대공약수 * 최소 공배수 = 두 수의 곱이다! 

 

따라서 최대공약수를 구했다면, 그냥 두 수를 곱해서 최대공약수를 나눠주면 최소공배수가 나온다.

 

수학적 원리가 재미있는 문제였다.