Algorithm | 유클리드 호제법

유클리드 호제법

유클리드 알고리즘의 경우 두수를 나누어서 원하는 값을 얻는 알고리즘이다.

동작의 원리의 경우 n 과 m 을 받아서 나눠 준다 그리고 후에

조건 절에 포함이 되지 않는다면 다음 단계로 result 값을 내려주고 두번째 인자를 1 번째 인자로 같이 내려준다.

유클리드 호제법의 경우 최대 공약수에 많이 사용을 한다.

그렇다면 최대 공약수는 무엇일까?

최대 공약수란 두 자연수에 대하여 공통된 약수 중에 가장 큰 수를 의미한다.

여기서 약수란 나누었을 때 떨어지는 수를 의미한다.

예를 드면 16 의 약수는 1, 2, 4, 8, 16 이며

20의 약수는 1, 2, 4, 5, 10, 20 으로 둘의 공통 약수는 1, 2, 4 이다

이 공통된 수중에 최대 값이 바로 최대 공약수 이다.

JAVA

JAVA 로 구현을 하기 위해서는 일단 재귀를 하려고한다.

최대 공약수와 더불어 최대 공배수를 구하려고 한다.

최대 공배수의 경우 n 과 m의 곱의 값에서 최대 공약수를 나누어 떨어지는 것을 말한다.

gcd 함수에서 조건절과 재귀를 통하여 구성을 하였다.

0이 면 첫번째 인자를 return 시키면 된다.

public class Euclidean {

    public static void main(String[] args) {

        int n = 24;

        int m = 18;

        int ans = gcd(n, m);

        // 최대 공약수
        System.out.println(ans);

        // 최소 공배수
        System.out.println(n * m / ans);

    }

    /**
     * 최대 공략수
     *
     * @param n
     * @param m
     * @return
     */
    public static int gcd(int n, int m) {

        if (m == 0) {
            return n;
        }

        return gcd(m, n % m);
    }

}