[Python] 2609번 최대공약수와 최소공배수

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

 

처음에 내가 생각한 코드는 다음과 같다. 두 수가 모두 나누어 떨어지는 수(최대공약수)를 for문을 통해 찾는 것이었다.

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

while n>1:
    if a%n==0 and b%n==0: #나머지=0
        break
    else:
        n-=1

print(n)
print(n*(a//n)*(b//n))

물론 이 코드를 제출해서 맞기는 했지만 다른 사람들의 코드를 보면서 얼마나 내가 무식하게 풀었는지 느낄 수 있었다.

from math import*

n,m=map(int,input().split())
print(gcd(n,m),lcm(n,m))

기본 math 라이브러리로 다음과 같이 풀 수 있다.

하지만 대부분 코테에서 라이브러 사용을 권장하지 않으므로 라이브러리를 사용하지 않고 풀게 되면 다음과 같다.

a,b=map(int,input().split())
m=a*b
while b != 0::
    a,b=b,a%b
print(a,m//a)

이는 유클리드 호제법에 따른 알고리즘이다. 

최대공약수, 최소공배수 문제는 유클리드 호제법을 따르면 간단하게 풀 수 있었다.

유클리드 호제법,,, 이산수학 시간에 배웠는데 이걸 까먹고 있었다니,,,

https://ddddewang.tistory.com/entry/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95%EC%9D%98-%EC%A6%9D%EB%AA%85-GCDabGCDbab

유클리드 호제법의 증명 | GCD(a,b)=GCD(b,a%b)

 

 

간략하게 유클리드 호제법을 증명하게 되면 (자세한 건 위의 다른 분이 증명해 주신 거 보시면 됩니다.)