[JAVA] 최대공약수와 최소공배수 구하기 (백준 : 2609번)

- 유클리드 호제법을 사용하여 재귀 혹은 반복문을 사용하여 구현한다.

   최대공약수와 최소공배수를 구하는 코드는 자주 나오기 때문에 외워두는 것이 좋다.

 

 

1. 재귀

import java.util.Arrays;
class Main {
    public int[] gcd_lcm(int n, int m) {
        int[] answer = new int[2];
        int big = (n > m)? n : m;
        int small = (n > m)? m: n;

        answer[0] = gcd(big, small);
        answer[1] = big * small / answer[0];

        return answer;
    }

    public int gcd(int a, int b) {
        if (a % b == 0) return b;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        Main m=new Main();
        System.out.println(Arrays.toString(m.gcd_lcm(15,18)));
    }
}

 

2. 반복문(while)

import java.util.Arrays;
class Main {
    public int[] gcd_lcm(int a, int b) {
      int[] answer = new int[2];
      int gcd=a*b, temp=1;
      
      while(temp!=0){
        temp=b%a;
        b=a;
        a=temp;
      }
      
      answer[0]=b;
      answer[1]=gcd/b;
      
      return answer;
    }
     public static void main(String[] args) {
        Main m = new Main();
        System.out.println(Arrays.toString(m.gcd_lcm(15,18)));
    }
}