최대공약수 최소공배수

최대공약수와 최소공배수를 Java에서 어떻게 구현하는지에 대한 설명입니다.

유클리드 호제법이라고도 불리는 방법으로 자바에서 이런 류의 문제를 풀 때 많이 쓰이며 저도 많이 쓰며 암기를 하고 있는 방식입니다. 

public static int gcd(int a, int b) {

    while (b!=0) {
        int r = a%b;

        a = b;
        b = r;
    }
    return a;
}

함수형으로 쓰고 싶으시다면 위와 같은 방식으로 쓰면 되고 그냥 쓰고 싶다면 아래와 같은 방식으로 쓰면 됩니다.

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      int A = Integer.parseInt(br.readLine());
      int B = Integer.parseInt(br.readLine());

      while (B != 0) {
         int r = A%B;

          A = B;
          B = r;
      }
        System.out.println(A);
    }
}

 

그럼 이제 최소공배수를 구하는 과정을 써보겠습니다.

코드는 위와 유사합니다. 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      int A = Integer.parseInt(br.readLine());
      int B = Integer.parseInt(br.readLine());

      int gcd = gcd(A,B); // 최대공약수

       int result = A*B / gcd;
        System.out.println(result);
    }
    public static int gcd(int A,int B) {
        while (B != 0) {
            int r = A%B;

            A = B;
            B = r;
        }
        return A;
    }
}