유클리드 호제법

두 수의 “최대공약수(GCD)”를 찾기 위한 알고리즘을 의미하며, 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될때까지 작동하는 방법이다.
이 때 작은 수가 최대공약수다.

예시

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
 1368 ＝ 180×7 ＋ 108
  180 ＝ 108×1 ＋ 72
  108 ＝ 72×1 ＋ 36
   72 ＝ 36×2 ＋ 0

따라서, 최대공약수는 36이다.

알고리즘

1. 입력으로 두 수 m,n(m>n)이 들어온다.
2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
3. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

재귀 방식으로 구현

 public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p%q);
 }

배열에 있는 모든 수의 최대공약수(GCD)

public static int gcd(int[] arr) {
    int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
        result = gcd(result, arr[i]);
    }
    return result;
}

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

반복문 방식으로 구현

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

최소공배수(LCM) 구현

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

배열에 있는 모든 수의 최소공배수(LCM)

public static int solution(int[] arr) {
    int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
        result = lcm(result, arr[i]);
    }
    return result;
}

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

public static int lcm(int a, int b) {
    return (a * b) / gcd(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,
https://adjh54.tistory.com/179