728x90
최대공약수
두 수의 공약수 중 가장 큰 수
최소공배수
두 수의 공배수 중 가장 작은 수
== (두 수의 곱)/ (최대공약수)
유클리드 호제법
최대공약수 구하기
두 수의 최대공약수는 두 수를 나눈 나머지와 나눈 수의 최대공약수와 같다.
A/B = C
GCD(A,B) = GCD(B,C)
B/C = D
GCD(A,B) = GCD(B,C) = GCD(C,D)
...
나머지가 0이 될 때, 나누는 수가 최대공약수이다.
만약
C/D = 0이라면
D가 최대공약수이다.
이것을 알고리즘으로 보면
GCD(A,B) = GCD(B,A%B)
if( A%B==0) return B
else GCD(B,A%B)
public int[] solution(int n, int m) {
int[] answer = new int[2];
answer[0]= GCD(n,m); //최대공약수
answer[1] =n*m/ GCD(n,m); //최소공배수
return answer;
}
int GCD(int a, int b) { //최대공약수 구하기
if(a%b==0)return b;
else return GCD(b,a%b);
}