[알고리즘] 백준 2609번 최대공약수와 최소공배수 Java 자바

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

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer strToken = new StringTokenizer(br.readLine(), " ");
        int a=Integer.parseInt(strToken.nextToken());
        int b=Integer.parseInt(strToken.nextToken());
        StringBuilder sb = new StringBuilder();
        int gcd=gcd(a,b);
        sb.append(gcd+"\n");
        sb.append(lcm(a,b,gcd)+"\n");
        System.out.println(sb);
    }

    //최대공약수를 구하는 알고리즘
    static int gcd(int x, int y) {
        if (y == 0) return x;
        else return gcd(y, x % y);
    }

    //최소공배수를 구하는 알고리즘
    static int lcm(int a, int b, int gcd) {
        return a * b / gcd;
    }
}

문제풀이 : 최대공약수를 유클리드호제법을 이용하여 구한 후 

최소공배수를 이용하여 최소공배수를 구한다.

 

유클리드 호제법 알고리즘 보러가기 : https://roomconerdeveloper.tistory.com/23

최소공배수는 두 수를 곱한 후 최대공약수로 나누면 나온다.