자바 - 최대공약수 & 최소공배수

1934 최소공배수

최대공약수 GCD : a, b에 대해 둘 다 나눌 수 있는 가장 큰 수
12, 18 > 6

최소공배수 LCM : a, b에 대해 공통의 배수 중 가장 작은 수
12, 18 > 36

import java.util.*;

public class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    Scanner in = new Scanner(System.in);
		int T = in.nextInt(); //테스트 케이스의 개수
		
		for(int i=0; i<T; i++){
		    int a = in.nextInt();
		    int b = in.nextInt();
		    
            //최대공약수
            int gcdResult = gcd(a, b); // gcd함수는 유클리드 호제법 사용
            
            //{(a * b) /최대공약수} 는 최소공배수 구하는 공식
            
            System.out.println((a * b) /gcdResult);
		}
		
	}
	
	
	//최대공약수 구하는 메서드
	public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    

}

유클리드 알고리즘

public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

두 수의 최대공약수는 작은 수(18)와 큰 수(48)를 나눈 나머지(48 % 18)의 최대공약수와 같음.

48 % 18 = 12 → gcd(18, 12)

18 % 12 = 6 → gcd(12, 6)

12 % 6 = 0 → 종료, 결과는 6