유클리드 호제법 - 최대공약수, 유한소수 판별하기

들어가기

---

최근 코딩테스트를 풀면서, 약수, 소인수분해, 소수, 최대공약수 ...등등 수학에 대한 내용들을 많이 접해왔다. 특히 최대공약수를 구하는 부분이 성가셔서 한 번 정리해보려고 한다.

 

 

728x90

 

유클리드 호제법

---

 

두 양의 정수 a, b (a > b)에 대하여 a = bq + r (0 ≤ r < b)이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉,

gcd⁡(a, b) = gcd⁡(b, r)

r=0이라면, a,b의 최대공약수는 b가 된다.

---

 

r은 나머지를 뜻한다. 결론적으로, a와 b의 최대공약수는 b와 a, b의 나머지인 r의 최대공약수와 같다는 것이다.

 

이를 코드로 구현해보면 아래와 같다.

// 최대공약수(GCD) 함수 (유클리드 호제법)
    private static int getGCD(int a, int b) {
        System.out.println(a + " " + b);
        if (b == 0) return a;
        return getGCD(b, a % b);
    }

 

위 함수는 b를 계속해서 나머지와 재귀적으로 비교하며 결국 b의 값이 나누어 떨어질 때 두 값의 최대 공약수를 리턴한다.

 

여기서 응용해서 유한 소수를 판별할 수 있는 식을 만들어 볼 수도 있는데,

유한 소수 판별 공식은 아래와 같다.

 

기약 분수로 나타내었을 때 분모의 소인수가 2, 5만 존재해야 한다.

 

분모와 분자를 최대 공약수로 나누면 기약 분수가 된다.

그러므로, 분모를 나누고, 해당 분모를 2, 5로 계속 나누어 준 값이 결국 1(몫)이 나오게 되면 유한소수인 것이다.

 

package solution;

class Solution {
    public static void main(String[] args) {
        System.out.println(solution(7, 20));
    }

    public static int solution(int a, int b) {
        int gcd = getGCD(a, b);
        b /= gcd; // 기약분수의 분모로 만듦

        // b를 2와 5로만 나눠서 1이 되면 유한소수
        while (b % 2 == 0) b /= 2;
        while (b % 5 == 0) b /= 5;

        return b == 1 ? 1 : 2;
    }

    // 최대공약수(GCD) 함수 (유클리드 호제법)
    private static int getGCD(int a, int b) {
        System.out.println(a + " " + b);
        if (b == 0) return a;
        return getGCD(b, a % b);
    }
}

 

 

 

 

출처

---

프로그래머스