[JAVA] 2609 최대공약수와 최소공배수- 문제풀이

● 해설

• a와 b를 입력을 받음.
• d는 최대공약수 이다. 함수를 이용하여 풀어준다
• gcd(greatest common divisor)함수는 최대공약수를 구하는 함수이며, 예시로 24와 18을 위 함수대로 따라간다면
• gcd(24,18) -> gcd(18, 6) -> gcd(6, 0) -> if문에 의하여 a를 반환
• 최소공배수는 왜 안 구하냐고 할 수 있겠지만,
•  최대공약수를 구해준 뒤 입력받은 두 수의 곱에서 최대공약수를 나눠주면 끝난다.
• 두 수의 '소인수분해'를 한 결과의 공통된 부분이 최대공약수, 즉 d 라는 것이다.
• 이해가 안된다면 a라는 것은 어떤 수 x * d 이고, b라는 것은 어떤 수 y * d 이다.
• 그렇다면 a * b == x*y*d*d가 된다. 여기서 d를 나눠주면 최소공배수 완성이다.

● 구현

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

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

        int d = gcd(a, b); // 최대공약수

        System.out.println(d);
        System.out.println(a * b / d);

    }

    // 최대공약수 재귀 방식
    public static int gcd(int a, int b) {
        if (b == 0)
            return a;

        // GCD(a, b) = GCD(b, r)이므로 (r = a % b)
        return gcd(b, a % b);
    }
}

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