[JAVA] 유클리드 호제법(GCD / LCD)

GCD (최대 공약수)

■ 정의

 1. 22 x 8 크기의 직사각형을 짧은 변(8)을 한 변으로 하는 정사각형으로 분할
 2. 정사각형을 제외한 8 x 6 직사각형을 짧은 변(6)을 한변으로 하는 정사각형으로 분할
 3. 남은 6 x 2 직사각형을 2 x 2 크기의 정사각형 3개로 분할
   ☞ 마지막까지 나누어 떨어진 정사각형의 한 변의 길이가 최대 공약수가 됨 

 

■ Code

import java.util.Scanner;

public class EuclidGCD {
    static int gcd(int x, int y){
        if(y == 0)
            return x;
        else
            return gcd(y, x % y);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        System.out.println("두 정수의 최대공약수를 구합니다.");
        System.out.print("두 정수를 입력하세요: ");
        int x = sc.nextInt(); int y = sc.nextInt();

        System.out.println("최대공약수는 " + gcd(x, y) + " 입니다.");
    }
}

 

---

LCD (최소 공배수)

■ 정의

두 수 A, B의 곱을 GCD로 나누어 주어 계산함
ex) A = 12, B = 6, GCD = 6 일 때, LCD = (12 x 6) / 6 = 12

 

■ Code (백준 No.1934)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int gcd(int x, int y){
        if(y == 0)
            return x;
        else
            return gcd(y, x % y);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            int lcd = (A * B) / gcd(A, B);
            System.out.println(lcd);
        }
    }
}

 

 

1934번: 최소공배수