6. 최대공약수 GCD

package _6;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		int num1, num2;
		Scanner sc = new Scanner(System.in);
		num1 = sc.nextInt();
		num2 = sc.nextInt();
		System.out.println(gcd(num1, num2));
		
	}
	
	public static int gcd(int num1, int num2) {

		int r = 0;
		
		r = num1 % num2;
		if(r == 0) {
			return num2;
		}
		
		return gcd(num2, r);
		
		/*
		while(true) {
			r = num1 % num2;
			if(r == 0) {
				return num2;
			}
			num1 = num2;
			num2 = r;
		}
		*/
	}
	
}

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.