BOJ 2609 최대공약수와 최소공배수 [Java]

BOJ 2609 최대공약수와 최소공배수

- 문제 링크

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

- 문제 해설

최대공약수와 최소공배수를 구하는 문제이다. 유클리드 호제법을 이용하면 풀 수 있다.
유클리드 호제법이 무엇인지 알아보자.
최대공약수를 구하는 알고리즘인데, 두 자연수 m, n (m > n)이 있다고 하자. 이 때, m을 n으로 나눈 나머지를 r이라고 하면, m과 m의 최대공약수가 n과 r의 최대공약수와 같다는 것이 유클리드 호제법이다.
이 성질을 이용하면 n을 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지 r''을 구하고, 다시 r'을 r''로 나눈 나머지를 구하는 과정을 계속 반복해서 나머지가 0이 되었을 때의 나누는 수가 m과 n의 최대공약수가 된다.
보기 좋게 그림으로 나타내보면 아래와 같다.

유클리드 호제법을 이용하여 최대공약수를 구하는 함수를 만들었다. 이 때, 함수가 비재귀함수인 것과 재귀함수인 것 2가지로 나눠서 풀어보았다.
최소공배수는 최대공약수를 알면 쉽게 구할 수 있다. 두 수가 m, n이라고 하면 최소공배수 = m x n / 최대공약수 이다.

- 코드 보기

- 비재귀함수 코드

import java.io.*;

public class Main
{        
    public static int gcd(int x, int y)
    {
        while(true)
        {
            int r=x%y;
            if(r==0)
                return y;
            x=y;
            y=r;
        }
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] str = br.readLine().split(" ");

        int a = Integer.parseInt(str[0]);
        int b = Integer.parseInt(str[1]);
        bw.write(Integer.toString(gcd(a, b)) + "\n" + Integer.toString((a * b / gcd(a, b))));

        br.close();
        bw.flush();
        bw.close();
    }
}

- 재귀함수 코드

import java.io.*;

public class Main
{
    public static int gcd(int x, int y)
    {
        if (y == 0)
            return x;
        else
            return gcd(y, x % y);
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] str = br.readLine().split(" ");

        int a = Integer.parseInt(str[0]);
        int b = Integer.parseInt(str[1]);
        bw.write(Integer.toString(gcd(a, b)) + "\n" + Integer.toString((a * b / gcd(a, b))));

        br.close();
        bw.flush();
        bw.close();
    }
}