Sohn SooKyoung

💛💚

최대 1 분 소요

[백준 2609번] 최대공약수와 최소공배수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package _1월_2주차;
 
import java.util.Scanner;
public class 백준_손수경_정답_2609 {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        int GCD = 0;
        int LCM;
        int i;
        int min = (num1 > num2) ? num2 : num1;
        int max = (num1 < num2) ? num2 : num1;
        for (i = min; i > 0; i--) {
            if ((num1 % i == 0) && (num2 % i == 0)) {
                GCD = i;
                break;
            }
        }
        LCM = min * (max / GCD);
        System.out.println(GCD);
        System.out.println(LCM);
    }
 
}
 
cs

GCD: 최대공약수
LCM: 최소공배수

최대공약수 구하기

입력받은 두 수 중 작은 수부터 하나씩 줄여가면서 두 수 모두 나누어 떨어지는 수를 최대공약수라고 지정하였다. 이때, i를 1씩 줄여나가면서 최대공약수를 구했으므로, 제일 처음 조건에 맞는 i가 최대공약수이다.

최소공배수 구하기

최소공배수는 최소공배수를 구하는 공식을 이용하여서 구했다. min * (max / GCD) 를 이용하였다.(최소공배수를 구할 때 사용하는 나누기식(?) 그거 이용해서 나온 규칙,,)

댓글남기기

참고