유클리드 호제법

최대공약수, 최소공배수를 구할때 사용하는 기본적인 알고리즘이다.

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

알고리즘

자연수 A와 B의 최대 공약수를 구할때
A와 B를 나눈 나머지 R이 0이 되는 값까지 서로를 치환하여 나누면 된다.

A = 24, B = 18 이라고 하자.
이 때의 나머지 R은 24 % 18 = 6 이 된다.

이후, B의 값을 A로, R의 값을 B의 자리로 치환한다. 그리고 다시 나누게 되면,
나머지 R은 18 % 6 = 0 이 된다. 즉 나머지R 이 0이 되었으므로,
마지막으로 나눈 6이 최대공약수가 된다.

최소공배수는 A x B / 최대공약수 이다.
따라서, 24 x 18 / 6 즉, 72가 된다.

자바 소스 코드

import java.util.Scanner;

public class Main {
    public static int gcd(int a, int b) {
        int r = a % b;

        while (r != 0) { // 나머지가 0이 될때까지 계속 치환하며 나눈다.
            a = b;
            b = r;
            r = a % b;
        }
        return b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();

        if (b > a) {
            int temp = a;
            a = b;
            b = temp;
        }

        int result = gcd(a, b);

        System.out.println(result);
        System.out.println(a * b / result);
    }
}