백준 2609 - 최대공약수와 최소공배수 (Python)

문제

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

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

풀이

a,b = map(int,input().split())

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

for i in range(max(a,b),a*b+1, max(a,b)):
    if i % min(a,b) == 0:
        print(i)
        break

처음에 문제를 봤을 때, 유클리드 호제법을 사용해야 될 것 같았다.

그래도 혹시나 해서 무지성으로 한번 풀어보았는데, 생각외로 시간초과가 안났다.

최대 공약수는 a,b 중 작은 값 부터 1씩 줄여가면서 a,b 두 수 모두 나누어 떨어지는 경우를 구했고,

최소 공배수는 a,b 중 큰 값의 배수 중 작은 것 부터 a,b 둘다의 배수인 경우를 찾았다.

 

유클리드 호제법은 관련 문제를 나중에 풀게되면 한번 다뤄보도록 하겠다.