[백준] CLASS2 2609 최대공약수와 최소공배수 - JAVA [자바]

 안녕하세요. 이번에는 백준 2609 최대공약수와 최소공배수 문제를 풀어보려고 합니다.

 

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

---

Problem

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

사진 1. 문제

---

Solution

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));
        StringBuilder sb = new StringBuilder();
        String[] str = br.readLine().split(" ");
        
        int a = Integer.parseInt(str[0]);
        int b = Integer.parseInt(str[1]);
        
        sb.append(gcd(a,b)).append("\n");
        sb.append(lcm(a, b));
        
        System.out.println(sb.toString());
    }
    
    public static int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a % b);
    }
    
    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}

 

 이번 문제는 최대공약수와 최소공배수를 구하는 문제이다. 최대공약수를 구하는 방법은 유클리드 호제법을 사용하면 쉽게 구해진다.

 

유클리드 호제법의 코드

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

 

 유클리드 호제법을 이용해서 최대공약수를 구한다. 최소공배수는 주어진 값들을 곱한 후 최대공약수로 나눠주기만 하면 해결된다. 향후 유클리드 호제법도 포스팅해 보도록 해야겠다.

---

Performance

사진 2. 실행 결과