GCD LCM = 유클리드 호제법

 

유클리드 호제법

최대공약수

gcd(a, b) = gcd(b, a% b)

 

gcd(24,18) = gcd(18,6) = gcd(6,0) 

즉 24와 18의 최대공약수는 6이 된다.

 

gcd(30,22) = gcd(22,8) = gcd(8,6) = gcd(6,2) = gcd(2,0)

30과 22의 최대공약수는 2가 된다.

 

 

최소공배수를 구할 때는 a, b로 구하는 것이 아니다.

왜냐하면 a와 b의 값은 이미 유클리드 호제법에 의해 변경된 값이기 때문에 a = 6, b = 2이기 때문이다.

따라서 A와 B에 사용자가 입력한 원본의 값을 저장하고 그 값을 활용해야 한다.

 

public class SBF_GCD_LCM {

        public static void main(String[]args){

		// 유클리드호제법

        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int A = a; // 원본 숫자 저장
        int B = b;
        
        int GCD = b;
        int LCM = GCD * (A/GCD) * (B/GCD); // 최소공배수

        while(true){
            int c = a%b;
            if(c==0) break;
            a = b;
            b = c;
        }

        System.out.println(GCD);
        System.out.println(LCM);

    }