공부 :: 최대공약수, 최소공배수, N개의 수 최소공배수 알고리즘

package gcd;
 
public class NormalGCD {
 
    // brute force
    public static void main(String[] args) {
        int num1= 30, num2= 66;
        
        int min = Integer.min(num1, num2); // 둘중 작은 수까지만 확인하면 됨
        
        int result=0;
        
        for(int i=min; i>=1; i--) {
            if(num1 % i == 0 && num2 % i == 0) {
                // 둘다 나누어 떨어지는 경우
                result = i;
                break;
            }
        }
        
        System.out.print("gcd : " + result);
        
        // 시간 복잡도 : O(min(num1,num2))
    }
}
 

package gcd;
 
public class FestGCD {
 
    // 유클리드 호제법을 이용
    // a mod b = 0이면, gcd = b
    // a mod b != 0 이면, b mod (a mod b) 를 만족
    public static void main(String[] args) {
        int a = 20;
        int b = 35;
        
        int mod = a % b;
        
        while(mod > 0) {
            a = b;
            b = mod;
            mod = a % b;
        }
        
        // 방법 1.
        System.out.println("gcd1 : " + b);
        
        int a2 = 30;
        int b2 = 66;
        // 방법 2. 재귀함수
        System.out.print("gcd2 : " + gcd(a2, b2));
    }
    
    public static int gcd(int a, int b) {
        if(a % b == 0) {
            return b;
        }
        return gcd(b, a % b);
    }
    
    // a mod b(범위 : 0 ~ b-1) 를 실행하면, 평균적으로 해당 범위의 절반 정도로 줄어 든다.
    // 그래서 시간 복잡도는 대략 O( log(min(a,b)) ) 이다.
}
 

숫자 a, b의 최대공약수를 G라 하자

a = Gx

b= Gy

로 표현 된다.

a, b의 최소 공배수(L)는

L= G * x * y = (a * b) / G

를 만족한다.

N개의 수 최소공배수

package gcd;
 
public class Nlcm {
    public long nlcm(int[] num) {
        int answer = num[0];
        int number = 0;
        for (int i = 1; i < num.length; i++) {
            // lcm = a * b / (a mod b) 
            answer = answer * num[i] / gcd(answer, num[i]);
        }
        return answer;
    }
    
    int gcd(int a, int b) {
        //a mod b
        int mod = a % b;
        while(mod > 0) {
            // b mod (a mod b)
            a = b;
            b = mod;
            mod = a % b;
        }
        return b;
    }
    
    public static void main(String[] args) {
        Nlcm c = new Nlcm();
        int[] ex = {8, 2, 6, 14};
        System.out.println(c.nlcm(ex));
    }
}