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

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

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

#2609 최대공약수와 최소공배수

n1,n2=map(int,input().split())

#첫째줄에 입력되는 두수

max_n1=n1
max_n2=n2

#최대 공약수로 만들 n1 n2

while max_n1%max_n2!=0:

res=max_n1%max_n2

max_n1=max_n2

max_n2=res

'''

유클리드 호제법을 이용한 최대 공약수 만들기

원리는 a를 b로 나눠서 나온 나머지 r을 다시 b에 나누는 과정을 반복할때 마지막에 나누어떨어질때의 b값이 최대공약수이다.

대충 원리는 이렇다 애초에 a에 b를 나눠서 나오는 나머지는 작아서 b가 되지 못한 것들이다. 이것을 b에 다시 나누면 즉 r을 b의 약수 취급을 하면 점점 쪼개지면서 나머지가 없다는 가정하에 b보다는 작은 약수들이 점점 생긴다. 끝에 진짜로 나머지가 없어져버리면 이제 그 약수는 b를 나눌수있게 되고 b는 a를 나눌수있으니 이 약수가 a를 나눌수 있게 된다. a와 b를 관통해서 다 나눌수 있는 약수중에서 가장 큰 수 즉 최대공약수가 되는 것이다.

'''

print(max_n2)

min_n1=n1
min_n2=n2

#n1 n2 가 하나 더 필요함. n1+=n1을 해버리면 2배씩 커져버림

while min_n1!=min_n2:

if min_n1>min_n2:

min_n2+=n2

else:

min_n1+=n1

print(min_n1)

 

#간단하게 생각하면 틀리는 문제 또한 호제법에 대한 이해가 필요한 문제 이것을 모르면 무조건 시간을 오래 쓰게 된다. 숙지할 것.