유클리드 호제법 (최대 공약수,공배수 구하기)

유클리드호제법.java

import java.util.Scanner;

public class EuclideanAlgorithm {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt(); // 제수
		int b = sc.nextInt(); // 피제수

		System.out.println(GCD(a, b));
		sc.close();
	}

	// 유클리드 호제법을 이용한 최대 공약수 구하기
	private static int GCD(int a, int b) {
		// 나머지가 0이라면 해당 수가 최종 최대 공약수이다.
		if (a % b == 0) {
			return b;
		}
		// 그렇지 않다면 제수를 다음 피제수로, 나머지를 다음 제수로 바꾸어 재귀를 진행한다.
		else {
			return GCD(b, a % b);
		}
	}
}