백준_2609_최대공약수와 최소공배수

풀이

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        /*
         * https://www.acmicpc.net/problem/2609
         * 최대공약수와 최소공배수
         */

        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int result1 = 0 ;
        int result2 = a*b ;

        while(a%b != 0){
            int c = a%b;
            a = b;
            b = c;
        }

        result1 = b;
        result2 = result2 / b;
        

        System.out.println(result1);
        System.out.println(result2);
        


    }

}

---

개념정리

❓ 최대공약수(GCD) 구하기

✔️ 최대공약수는 두 수 a , b 가 있을 때 둘다 나눌 수 있는 가장 큰 수이다

✔️ 24와 18의 최대공약수는 24와 18을 모두 나눌 수 있고, 24 / 18 의 나머지 6도 나눌 수 있어야 한다.

✔️ 따라서, 나머지가 0으로 떨어지는 수가 나올 때 까지 약수와 나머지 간의 나누기 연산을 반복한다.

예시 1 : 24 / 18 -> 18 / 6 -> 나머지가 0 -> 최대공약수는 6

예시 2 : 42/ 30 -> 30/12 -> 12/6 -> 최대공약수는 6

 

❓ 최소공배수(LCM) 구하기

✔️ 최소공배수는 두 수 a, b 가 있을 때 공통배수 중에서 가장 작은 수이다.

✔️ 확실한 공배수는 두 수 a와 b를 곱한 수이다.

✔️ 이 수에는 최대공약수가 두번 들어가 있다. 따라서 중복된 최대공약수를 한번 나눠서 제거해준다.

예시 1: 12 * 18 = (6*2) * ( 6*3) = 6 * 6 * 2 * 3 -> 6을 한번 나누어 제거-> 최소공배수는 36