Skip to main content

[Java] 최대공약수, 최소공배수

1. 변수명 명명법

  • gcd(Greatest Common Divisor) : 최대공약수
  • lcm(Lease Common Multiple): 최소공배수

2. 최대공약수(GCD) 구하는 대표 메서드

2.1 유클리드 호제법 (재귀 버전)

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

2.2 반복문 버전

public int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

3. 최소공배수(LCM) 구하는 공식과 메서드

  • 공식 : lcm(a,b) = (a * b) / gcd(a, b)
  • 최소공배수를 구하려면 최대공약수를 먼저 구해야 함
public int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

4. 자바 내장 메서드 (Java 8 이상)

Java 8 이상부터는 java.math.BigInteger 클래스에 GCD 메서드가 있어서 큰 수 계산에 유용하다.

import java.math.BigInteger;

BigInteger a = BigInteger.valueOf(12);
BigInteger b = BigInteger.valueOf(18);
BigInteger gcd = a.gcd(b);

참고 자료 : chatGPT

Back to top