[Java] 최대공약수와 최소공배수 구하기

자바를 공부하다 보면 자연스레 알고리즘 문제도 풀게 되는데요. 알고리즘 문제에 단골손님으로 등장하는 것이 바로 두 숫자의 최대공약수와 최소공배수를 구하는 문제가 꼭 있습니다. 이번 포스팅에서는 두 수의 최대공약수와 최소공배수를 구하는 방법에 대해서 알아보도록 하겠습니다. 예제는 두 개의 숫자를 입력받아서 두 개의 숫자의 최대공약수와 최소공배수를 구하는 알고리즘을 준비했습니다.

 

 최대공약수와 최소공배수 구하기 

첫번째 방식

import java.util.Arrays;
import java.util.Scanner;

class TryHelloWorld {
    public int[] gcdlcm(int a, int b) {
      int[] answer = new int[2];
      int temp=1;
      int gcd=a*b;
      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) {
      int num1,num2;
      Scanner sc = new Scanner(System.in);
      System.out.println("두개의 숫자를 입력해주세요");
      num1 = sc.nextInt();
      num2 = sc.nextInt();
      TryHelloWorld c = new TryHelloWorld();
      System.out.println(Arrays.toString(c.gcdlcm(num1 , num2)));
    }
} 

 

두번째 방식

import java.util.Arrays;
import java.util.Scanner;

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) {
      int num1,num2;
      Scanner sc = new Scanner(System.in);
      System.out.println("두개의 숫자를 입력해주세요");
      num1 = sc.nextInt();
      num2 = sc.nextInt();
      TryHelloWorld c = new TryHelloWorld();
      System.out.println(Arrays.toString(c.gcdlcm(num1 , num2)));
    }
}