[Java] 백준 풀기 2609 - 최대공약수와 최소공배수

자바 백준 2609번

브론즈 1

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

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

 

 

 

 

 

문제 보기

분류: 수학, 정수론, 유클리드 호제법

 

 

 

 

 

문제 풀기

유클리드 호제법을 이용하여 최대공약수를 구한다.

 

Wikipedia: 유클리드 호제법

 

 

 

두 수가 아래와 같이 정해졌을때,
18 24

 

num2가 0이 될때까지, 함수의 파라미터 num1과 num2의 위치 바꿈과 동시에 num1 % num2의 나머지를 구하는 재귀함수를 돌린다.
num1: 18, num2: 24
num1: 24, num2: 18
num1: 18, num2: 6
num1: 6, num2: 0

 

output:
6
72

 

 

최대공약수는 num2가 0일때 num1 결과를 출력한다.

 

최소공배수는 두 수의 곱에 중복된 최대공약수 한 번을 나누어 그 결과를 출력한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

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

        // 두 개의 자연수 입력받기
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();

        // 최대 공약수 구하기
        int gcdResult = greatestCommonDivisor(num1, num2);

        // 최소 공배수 구하기
        int lcmResult = leastCommonMultiple(num1, num2);

        // 결과 출력
        System.out.println(gcdResult);
        System.out.println(lcmResult);
    }
    
    // 최대 공약수를 구하는 메서드
    private static int greatestCommonDivisor(int num1, int num2) {
        // System.out.println("num1: " + num1 + ", num2: " + num2);  // TEST PRINT
        if (num2 == 0) {
            return num1;
        } else {
            return greatestCommonDivisor(num2, num1 % num2);
        }
    }

    // 최소 공배수를 구하는 메서드
    private static int leastCommonMultiple(int num1, int num2) {
        return (num1 * num2) / greatestCommonDivisor(num1, num2);
    }

}



/*

input:
18 24

output:
num1: 18, num2: 24
num1: 24, num2: 18
num1: 18, num2: 6
num1: 6, num2: 0
num1: 18, num2: 24
num1: 24, num2: 18
num1: 18, num2: 6
num1: 6, num2: 0
6
72

*/