알고리즘 - 최대공약수 계산(유클리드 호제법) java 예제

유클리드 호제법

• 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘이다.
• 두 자연수 A, B에 대하여 A를 B로 나눈 나머지를 R이라고 할 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

EX) 192와 162의 최대 공약수 구하기

1. A = 192, B = 162이다.

2. A를 B로 나눈 나머지 R = 30이다.

3. 162를 30으로 나눈 나머지는 

4. 이 과정을 반복하여 한 쪽이 나누어 떨어질 때까지 반복한다.

5. 최대공약수는 나누어 떨어지기 직전의 나머지인 6이다.

JAVA로 유클리드 호제법을 활용한 최대공약수 구하기

- 최대공약수를 구하기 위한 gcd함수를 구현하여 나누어 떨어질 때까지 재귀적으로 구현한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Euclidean {
	//최대공약수 계산(유클리드 호제법) 예제
	public static int gcd(int a, int b) {
		if(a % b == 0) {
			return b;
		}else {
			return gcd(b, a % b);
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int a = Integer.parseInt(br.readLine());
		int b = Integer.parseInt(br.readLine());
		
		//a와 b의 최대공약수 구하기
		System.out.println(gcd(a, b));
		br.close();
	}

}