[JAVA] 최대공약수, 최소공배수 구하기

최대공약수, 최소공배수 구하기

---

공약수 : 두 개 이상의 자연수(양의 정수) 중에서 공통된 약수

최대공약수 : 공약수 중 제일 큰 약수

서로소 : 공약수가 1뿐인 2개 이상의 자연수

 

최대공약수

 - 소인수분해로 구하기 (서로소가 나올 때까지 소수로 계속 나눔)

 - 출처 : https://mathbang.net/202

소인수분해

 - 최대공약수는 6x2 = 12

 

공배수 : 2개 이상의 자연수 중에서 공통된 배수

최소공배수 : 공배수 중 제일 작은 공배수

 

최소공배수

 - 위 사진에서 최소공배수는 6x2x5x4 = 240 이다.

---

소인수분해를 이용한 최대공약수, 최소공배수 구하기

// 소인수분해를 이용한 풀이
// 결과값 = 공약수들 + 서로소들
public static int[] factorization(int n, int m){
    int divisor = 2;
    List<Integer> facts = new ArrayList<Integer>();
    int[] retData;

    while(true){
        if ((n % divisor == 0) && (m % divisor == 0)){
            facts.add(divisor);
            n /= divisor;
            m /= divisor;
        }
        else{
            if (divisor > n || divisor > m){
                facts.add(n);
                facts.add(m);
                break;
            }

            divisor++;
        }
    }

    retData = new int[facts.size()];
    for(int i=0; i<facts.size(); i++){
        retData[i] = facts.get(i);
    }

    return retData;
}

---

 

유클리드 호제법을 이용한 최대공약수, 최소공배수 구하기

 - 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고하면 (단, a>b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r0를 구하고 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a, b의 최대 공약수이다.

 - 출처 : 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

 

// gcd : 최대공약수
// lcm : 최소공배수
public static int[] gcdlcm(int n, int m){
    int gcd;
    int lcm;

    gcd = gcd(n, m);
    lcm = (n * m) / gcd;

    return new int[] { gcd, lcm };
}

public static int gcd(int n, int m){
    // 나머지가 0이면
    if (m == 0){
        // 나눈값 반환
        return n;
    }

    // 나눈 수, 나머지 값
    return gcd(m, n % m);
}