[Java] 최대공약수(GCD), 최소공배수(LCM)

 

최대공약수(GCD)

    // 반복문 사용
    public static int gcd(int a, int b) {
        while( b!= 0) {
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }

    // 재귀함수 이용
    public static int gcd1(int a, int b) {
        if(b == 0)
            return a;
        else
            return gcd1(b, a%b);
    }

 

최소공배수(LCM)

    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }