최대공약수와 최소공배수

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환해주는 gcdlcm 함수를 완성해 보세요. 배열의 맨 앞에 최대공약수, 그 다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 gcdlcm(3,12) 가 입력되면, [3, 12]를 반환해주면 됩니다.

최소공배수 : n1 * n2 / 최대공약수 

최대공약수 : 유클리드 호제법

유클리드 호제법

유클리드 호제법(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다.

호제법이란, 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다.

풀이

import java.util.Arrays;
class TryHelloWorld {
    public int[] gcdlcm(int a, int b) {
        int[] answer = new int[2];
		int num_1 = a;
		int num_2 = b;
		int mix = a * b;
		int mod = 1;
      
      	// 큰수를 작은수로 나누기 위해 num_1 자리에 큰수 지정(SWP)
		if(num_1 < num_2){
            num_1 = num_1 ^ num_2;
          	num_2 = num_1 ^ num_2;
          	num_1 = num_1 ^ num_2;
        }	        
      	// 나머지가 0이 되는 순간 큰수가 최대공약수 [유클리드 호제법]
      	while(mod > 0){
      	        mod = num_1 % num_2;
                num_1 = num_2;
                num_2 = mod;
        }	
      	answer[0] = num_1;
      	answer[1] = (a * b) / answer[0];
      	return answer;
    }
    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        TryHelloWorld c = new TryHelloWorld();
        System.out.println(Arrays.toString(c.gcdlcm(3, 12)));
    }
}

다른 풀이

import java.util.Arrays;

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);
   }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        TryHelloWorld c = new TryHelloWorld();
        System.out.println(Arrays.toString(c.gcdlcm(3, 12)));
    }
}