유클리드 호제법

두 양의 정수 a,b에 대하여 (a>b)
a = bq+r ( 0<=r<b)라 하면
a,b의 최대공약수는 b,r의 최대공약수와 같다
이 때, r =0이라면 a,b의 최대공약수는 b가 된다

---

출처: 나무위키

즉 나머지가 0이 나올 때 까지 나머지로 계속 나눠주면 되는 것이다. 나머지가 0이 되는 순간 나눈 수가 a,b의 최대공약수가 되고, a*b=최소공배수*최대공약수 이므로 최소공배수 또한 구할 수 있다.

소스코드

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

public class Main{
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int count = in.nextInt();

        for (int i=0; i<count; i++){
            int a =in.nextInt();
            int b = in.nextInt();
            if (a>=b){
                System.out.println((a*b)/euclid(a,b));
            } else {
                System.out.println((a*b)/euclid(b,a));
            }
        }
    }


    public static int euclid(int a,int b){
        if (a%b==0) return b;
        else {
            return euclid(b,a%b);
        }
    }
}

백준 1934번
유클리드 호제법으로 최소공배수를 구하는 코드다