공약수

[백준] 2436 - 공약수 (자바 Java)

[Gold V] 공약수 - 2436 문제 링크 성능 요약 메모리: 12872 KB, 시간: 108 ms 분류 브루트포스 알고리즘(bruteforcing), 유클리드 호제법(euclidean), 수학(math), 정수론(number_theory) 문제 설명 어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다. 이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 예를 들..