2609번

[백준 2609번][C++] 최대 공약수와 최소 공배수

유클리드 호제법을 이용한 최대공약수와 최소공배수 구하기 코드는 어렵게 적어놓았지만 기본 개념은 상당히 간단합니다! 두 수를 A와 B라고 했을때 A%B = 0 이라고 했을 때 A는 B의 배수이기 때문에 최대 공약수는 B입니다 이런 사실에 대해 A%B가 0이 아닌 C라고 가정했을 때 A와 B의 최대 공약수는 B와 C의 최대공약수와 같다는 원리가 유클리드 호제법입니다. 따라서 ? % ? = ? 의 기본식에서 나머지가 0이 될 때까지 값들을 업데이트 해준다면 쉽게 찾을 수 있습니다 또한 최소공배수와 최대공약수를 곱한 값은 두 수를 곱한 값과 동일합니다. #include using namespace std; //유클리드 호제법을 이용한 최대 공약수 구하기 int gcd(int n1, int n2) { int mo..