[백준 #5344] GCD(최대공배수) 문제

---

0. 먼저 읽어보기

 

GCD 알고리즘

GCD(최대공약수, Greatest Common Divisor) 알고리즘

 

 

 

---

https://www.acmicpc.net/problem/5344

 

1. 문제

The greatest common divisor (GCD) of two integers is the largest positive integer that divides the numbers without a remainder. For example, GCD of 8 and 12 is 4. You will write a program that finds the gcd of two positive integers.

두 정수의 최대 공약수(GCD)는 두 수를 나누어떨어지게 하는 가장 큰 양의 정수입니다. 예를 들어, 8과 12의 GCD는 4입니다. 두 개의 양의 정수의 GCD를 찾는 프로그램을 작성하세요.

 

입력

The first line of input will be a positive integer, n, indicating the number of problem sets. Each problem set consist of two positive integers, separated by one or more spaces. There are no blank lines in the input.

입력의 첫 줄은 양의 정수 n으로, 문제 세트의 개수를 나타냅니다. 각 문제 세트는 하나 이상의 공백으로 구분된 두 개의 양의 정수로 구성됩니다. 입력에는 빈 줄이 없습니다.

 

출력

For each problem set print the gcd of the two positive integers. Print each gcd on a separate line.

각 문제 세트에 대해 두 양의 정수의 GCD를 출력하십시오. 각 GCD를 별도의 줄에 출력하십시오.

 

예제 입력

3
54 24
33 22
41 103

 

예제 출력

6
11
1

해결 코드

유클리드 알고리즘(유클리드 호제법)을 통해 해결하였다. (해당 개념은 이전 글을 참고)

import java.util.Scanner;
import java.lang.Math;

public class Main {

    public static int GCD(int m, int n) {

        while(n != 0) {
            int temp = m;
            m = n;
            n = temp % n;
        }

        return m;
    }

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

        int n = scanner.nextInt();

        for(int i=0; i<n; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            int s = Math.max(a, b);
            int k = Math.min(a, b);

            System.out.println(GCD(s, k));
        }
    }
    
}