[기초] 최소공배수 GCD & 최대공약수 LCM JAVA

최대공약수 = GCD (Greatest Common Divisor)
-> 유클리드 호제법 : O(logN)의 시간복잡도를 갖는다
    1. 입력 받은 두 수중 큰 수를 작은 수로 나눈다

    2. 나눈 나머지가 0면 작은 수를 return 

    3. 나눈 나머지가 0이 아니면 작은 수와 나머지를 재귀로 자기자신을 다시 호출

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
       
        int loop = Integer.parseInt(reader.readLine());
        for(int i=0; i<loop ; i++) {
	        String[] inputNum = reader.readLine().split(" ");
	        int big = Math.max(Integer.parseInt(inputNum[0]), Integer.parseInt(inputNum[1]));
	        int small = Math.min(Integer.parseInt(inputNum[0]), Integer.parseInt(inputNum[1]));
	        int gcd = getGcd(big, small);
	        System.out.println(gcd);
        }
        reader.close();
	}
	
	public static int getGcd(int first, int second) {
		int remain = first %second;
//		재귀
		if(remain!=0) {
			return getGcd(second, remain);
		}else {
			return second;
		}
	}
}

최소공배수 = LCM (Least Common Multiple)
->최소공배수 = 두수의 곱 / 최대공약수

->위 코드에서 출력 부분에

System.out.println(big * small /gcd);

이렇게 바꿔주면 최소공배수 구하는 알고리즘이 된다.

 

위 코드로 풀이 가능한 문제

백준 : 2609, 1934