java) 최소 공배수, 최대 공약수 - 유클리드 호제법

* 방법 *

  1. 입력받은 두 수 중 큰수를 결정
  2. 큰수를 작은 수로 나눈다
  3. 나머지가 0 일경우
     최대공약수 = 작은수
     최소공배수 = (두수의곱)/최대공약수
  4. 나머지가 0이 아닐경우
       큰수   = 작은 수
       작은수 = 나머지 로 정하고
     2번부터 다시 반복

 

a를 b로 나눈 나머지를 r이라고 했을 때 a,b 의 최대공약수는 b,r 의 최대공약수와 같다

즉 b,a%b의 최대 공약수와 같게 된다. 이를 r이 0이 될때까지 반복하면 그 값이 최대공약수가 된다.

 

 

< 내 코드 >

public int[] solution(int n, int m) {
int a = n;
int b = m;
int[] answer=new int[2];

int max, min;
if(a>b)
{
max = a;
min= b;
}
else {
max = b;
min =a;
}

while(min!=0) {
int temp=min;
min =  max%min;
max = temp;
}

answer[0] = max;
answer[1] = (int)a*b/max;

return answer;
}

 

 

 

 

<다른 사람 코드>

class TryHelloWorld {

     public int[] gcdlcm(int a, int b) {

        int[] answer = new int[2];

        answer[0] = gcd(a,b);

        answer[1] = (a*b)/answer[0];

        return answer;

}

     public static int gcd(int p, int q) { 

          if (q == 0) return p;

         return gcd(q, p%q); }

}