[자바] 최소 공배수(LCM) 구하는 방법

 

 

 

두 수 a, b의 최소공배수(LCM)

 

 

a*b <= 2,147,483,647 을 만족할 때 사용한 코드이다. 즉, int 타입의 범위를 벗어나지 않을 때 사용 가능하다.

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

static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

 

만약 a*b > 2,147,483,647 이라면 나눗셈을 먼저하고 곱셈을 하면 된다.

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

static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}