유클리드 호제법
-
[백준 2609] - [수학 최소공배수 최대공약수] - 최대공약수와 최소공배수(JAVA)알고리즘/수학 2018. 12. 3. 15:35
문제 링크 : https://www.acmicpc.net/problem/2609 이문제는 입력 받는 두 수의 최대 공약수와 최소 공배수를 구하는 문제이다. 최대 공약수는 두 개 이상의 수가 공통으로 가지는 약수 중 가장 큰 수를 말한다. 두 수 18과 24가 있다 하면 각각의 약수는 다음과 같다.18의 약수 : 1, 2, 3, 6, 9, 1824의 약수 : 1, 2, 3, 4, 6, 8, 12, 24이들 약수중에 공통으로 가지는 약수는 {1, 2, 3, 6}이고 이들 중 가장 큰 수는 6이 된다. 먼저 18의 약수를 구하고 24의 약수를 구한다음 각 각 의 약수중에서 공통 약수를 추려낸 뒤 그중 제일 큰 수를 찾았다. 수의 크기가 작은 경우 빠르게 구할 수 있겠지만 만약 수가 큰 수라면 어떻게 될까?각각..