JAVA 백준 9884번 Euclid

문제

The famous Euclidean algorithm is found in Book VII of the Elements. The Elements was written in 300 B.C. by the Greek mathematician Euclid. It is rumored that King Ptolemy, having looked through the Elements, hopefully asked Euclid if there were not a shorter way to geometry, to which Euclid sternly answered: “In geometry there is no royal road!” Probably we should not blame the King for looking for short cuts, for there are thirteen books in the Elements ! The books consist mainly of the mathematical knowledge amassed by Euclid, and possibly some discoveries of his own. The great achievement of Euclid is the beautifully systematic presentation of material as an organic whole. The Elements remained a standard work for over two thousand years.
The original Euclidean algorithm uses subtraction to find the greatest common divisor (gcd) of two positive integers A and B. It is based on the observation that a common divisor of A and B is also a common divisor of the integers min(A, B) and max(A, B) − min(A, B). Thus the gcd of A and B can be found as

1. If A = B then the gcd is B and the algorithm ends.
2. Replace A by max(A, B) − min(A, B), B by min(A, B). Go to Step 1.
   With the original Euclidean algorithm or otherwise, find the gcd of two positive integers.
   Let A = 24, B = 15. The original Euclidean algorithm computes
3. A = 24 − 15 = 9, B = 15
4. A = 15 − 9 = 6, B = 9
5. A = 9 − 6 = 3, B = 6
6. A = 6 − 3 = 3, B = 3
   That is, gcd(24, 15) = 3.

입력

The input contains one line. The line contains two positive integers (each not larger than 32767) separated by spaces.

24 15

출력

The output contains one integer which is the gcd of the two given positive integers.

3

알고리즘 분류

유클리드 호제법(euclidean), 구현(implementation), 수학(math), 정수론(number_theory)

힌트

양의 두정수 32767 보다 작거나 같다.
최대공약수를 구하는 문제입니다.

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        System.out.println(GCD(A, B));
    }

    // greatest common divisor
    static int GCD(int a, int b) {
        if (b == 0) return a;
        return GCD(b, a % b);
    }

    // least common multiple
    static int LCM(int a, int b) {
        return (a * b) / GCD(a, b);
    }
}