[Python]수학3 백준 2609

   문제

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

먼저 앞전에 사용했던 약수를 구하는 방법을 통해 하나의 약수를 모두 구하고 그 약수

들로 다른 수를 나누어보며 최대공약수를 구하고 최소공배수는 두수의 곱에서 최대공약

수를 나눈값으로 구했다.

 

n,m=map(int,input().split())
 
factor=[]
#n의 약수를 모두 하기
p=2
tmp=n
while p*p<=tmp:
    if tmp%p==0:
        factor.append(p)
        tmp//=p
    else:
        p+=1
if tmp>1:
    factor.append(tmp)
#m을 n의 약수로 나누어보며 최대공약수 구하기
mul=1
tmp=m
for i in range(len(factor)):
    if tmp%factor[i]==0:
        mul*=factor[i]
        tmp//=factor[i]
 
print(mul)
print(n*m//mul)

이 방법 외에 유클리드 호제법이라는 최대공약수를 구하는 알고리즘이 있었다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

어떤 분들은 바로 이해가 되겠지만 저는 아래 유튜브를 통해 이해할수 있었습니다. 

증명은 6분50초부터 보면될거 같습니다.

https://www.youtube.com/watch?v=hqTW8HdjBVw

n,m=map(int,input().split())
 
if m>n:
    n,m=m,n
 
g=m
r=n%m
while r!=0:#유클리드 호제법
    tmp=r
    r=g%r
    g=tmp
 
print(g)
print(n*m//g)