프로그래머스 Java / Ruby : 최대공약수와 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

---

최대공약수는 유클리드 호제법을 이용하면 편리하게 구할 수 있다.

유클리드 호제법이란?

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

최소공배수는 최대공약수가 가지지 않았던 모든 약수를 곱해주면 되므로

둘을 곱하고 약수로 나누어주면 된다.

 

- Java

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        answer[0]=gcd(Math.max(n,m),Math.min(n,m));
        answer[1]=(int)n*m/answer[0];
        return answer;
    }
    static int gcd(int a, int b){
        while(a!=0){
            a=a%b;
            if(a==0) return b;
            int c = a;
            a=b;
            b=c;
        }
        return -1;
    }
}

 

- Ruby

def solution(n, m)
    answer = []
    answer.append(gcd(n,m))
    answer.append(n*m/answer[0])
    return answer
end

def gcd(a,b)
    if a<b
        a,b=b,a
    end
    while a!=0
        a=a%b
        if a==0
            return b
        end
        a,b=b,a
    end
end