class2 - 2609번 최대공약수와 최소공배수 (자바)

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

 

이 문제에서 필요한 개념

유클리드 호제법

최대공약수를 구하는 알고리즘.

큰 수를 작은 수로 나누어 떨어지게 한 뒤, 수를 반복적으로 수행하여 나머지 0이 될때까지 작동함.

public static int gcd(int num1, int num2) {
    if (num2 == 0) return num1;
    return gcd(num2, num1 % num2);
}

위와 같이 재귀방식으로 최대공약수를 구한다.

여기서 주의할점은 큰수를 num1로, 작은수를 num2로 둬야한다는 점. 안그러면 무한루프에 빠지게 된다...

 

최소공배수 = (두 수의 곱) / 최대공약수

 

 

문제 풀이

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            
            // 최대공약수 구하기
            int gcd = gcd(num1, num2);
            
            // 최소공배수 구하기
            int lcm = num1 * num2 / gcd;
            
            bw.write(String.valueOf(gcd)+"\n"); // 최대공약수
            bw.write(String.valueOf(lcm)+"\n"); // 최소공배수
           
            br.close();
            bw.flush();
            bw.close();
		}
		catch (IOException e) {
          System.out.println("IOException 발생");
		}
		
	}
	
	public static int gcd(int num1, int num2) {
	    if (num2 == 0) return num1;
	    return gcd(num2, num1 % num2);
	}
}

 

유클리드 호제법을 알고있으면 간단하게 풀 수 있는 문제였다.