BOJ 2609 최대공약수와 최소공배수 [Java]

BOJ 2609 최대공약수와 최소공배수 - 문제 링크 https://www.acmicpc.net/problem/2609 - 문제 해설 최대공약수와 최소공배수를 구하는 문제이다. 유클리드 호제법을 이용하면 풀 수 있다. 유클리드 호제법이 무엇인지 알아보자. 최대공약수를 구하는 알고리즘인데, 두 자연수 m, n (m > n)이 있다고 하자. 이 때, m을 n으로 나눈 나머지를 r이라고 하면, m과 m의 최대공약수가 n과 r의 최대공약수와 같다는 것이 유클리드 호제법이다. 이 성질을 이용하면 n을 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지 r''을 구하고, 다시 r'을 r''로 나눈 나머지를 구하는 과정을 계속 반복해서 나머지가 0이 되었..

→2021.07.26