Computer ScienceAlgorithmProblem Solving

27. 최소공배수, 최대공약수 (GCD, 유클리드 호제법)

최대공약수, 최소공배수를 다룬 문제가 나오면 GCD나 유클리드 호제법을 반드시 알고 있어야한다!
알아보자!

GCD

최대공약수를 구하는 알고리즘
두 수 중 작은 수가 0이 될 때까지 반복하면 된다.
큰수는 작은수가 되고, 작은수는 큰수를 작은수로 나눈 나머지가 된다.

1
2
3
4
5
6
7
8
9
//a>b
int GCD(int a, int b){
    while(b !=0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

실제 백준 문제로 확인해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;
import java.io.*;
public class Main{
    public static int GCD(int a , int b){
        while(b != 0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int small = GCD(a, b);
        int big = (a*b)/small;
        System.out.printf("%d\n%d",small,big);        
    }
}
Share