min(n, m)까지 탐색

  i=1부터 min(n, m)까지 for문을 돌려서 n, m에 둘 다 나누어떨어지는 수 중 가장 큰 수를 구한다. 그것이 바로 최대공약수이다. 최소공배수는 최대공약수와 n, m의 관계로부터 쉽게 구할 수 있다.

public class s {
    public static void main(String[] args) {
        int n = 20;
        int m = 8;
        int gcd = gcd(n, m);
        int lcm = lcm(n, m);
    }
	//최대 공약수
    public static int gcd(int n, int m){
        int gcd = 1;
        for (int i = 1; i < Math.min(n, m); i++) {
            if ((n % i == 0) && (m % i == 0))
                gcd = i;
        }
        return gcd;
    }
    //최소 공배수
    public static int lcm(int n, int m){
        return n*m/gcd(n, m);
    }
}

시간 복잡도는 O(n)으로 괜찮긴 하지만 아쉽다.

유클리드 호제법

  유클리드 호제법으로 최대공약수를 구한다. 최소공배수는 여기서도 마찬가지로 최대공약수와 n, m의 관계로부터 쉽게 구할 수 있다.

public class s {
    public static void main(String[] args) {
        int n = 20;
        int m = 8;
        int gcd = gcd(n, m);
        int lcm = lcm(n, m);
    }
	//최대 공약수
    public static int gcd(int n, int m){
        if (m == 0){
            return n;
        }
        return gcd(m, n % m);
    }
    //최소공배수
    public static int lcm(int n, int m){
        return n * m / gcd(n, m);
    }
}

더 간단하고 시간복잡도는 O(log(n))이다.

참고 : 유클리드호제법