자바(백준) 2609 최대공약수와 최소공배수

풀이 방법 1

두 수를 입력받아 두 수중 최대 최솟값을 구한다. 그래서 for문으로 1부터 최솟값까지 i로 나누어 둘 다 나머지가 0이 되는 것 중에 최댓값을 구한다. 이것이 최대공약수이다. 그리고 두 수를 곱하고 최대공약수로 나눈 것이 최소공배수가 된다.

 

사용 개념 1

최소 공배수 = 두 수 곱 / 최대 공약수

 

코드 1(유클리드 호제법 사용 X)

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        int num1 = Integer.parseInt(st.nextToken());
        int num2 = Integer.parseInt(st.nextToken());
        int max_aliquot = Integer.MIN_VALUE;
        int max = (num1 >= num2) ? num1 : num2;
        int min = (num1 >= num2) ? num2 : num1;
        
        for(int i = 1; i <= min; i++){
            if(max % i == 0 && min % i == 0)
                if(i > max_aliquot)
                    max_aliquot = i;
        }
        sb.append(max_aliquot + "\n");
        int min_multiple = num1 * num2 / max_aliquot;
        sb.append(min_multiple + "\n");
        System.out.print(sb);
    }
}

풀이 방법 2

두 수를 입력받아 두 수중 최대 최솟값을 구한다. 그래서 gcd메소드를 호출하고, gcd메소드는 유클리드 호제법을 사용하여 최대공약수를 구한다. 그리고 풀이 방법 1과 비슷하게 최소 공배수는 두 수 곱 / 최대공약수로 구한다.

 

사용 개념 1

유클리드 호제법

 

코드 1(유클리드 호제법 사용 O)

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        int num1 = Integer.parseInt(st.nextToken());
        int num2 = Integer.parseInt(st.nextToken());
        
        int max = (num1 >= num2) ? num1 : num2;
        int min = (num1 >= num2) ? num2 : num1;
        
        int result1 = gcd(max,min);
        int result2 = max * min / result1;
        
        sb.append(result1 + "\n" + result2);
        System.out.print(sb);
    }
    static int gcd(int max, int min){
        while(min != 0){
            int temp = max % min;
            max = min;
            min = temp;
        }
        return max;
    }
}