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

◇ 유클리드 호제법 : 최대공약수를 구하는 알고리즘

최대공약수(GCD) : 유클리드 호제법을 통해 구한다.

최소공배수(LCM) : 두 수의 곱을 최대공약수(GCD)로 나눈다.

1. 두 수 A, B(A > B)에 대해 A / B의 나머지 C를 계산
2. B를 C로 나눈 나머지 D를 계산
3. C를 D로 나눈 나머지 E를 계산
4. 위 과정을 반복하여 나머지가 0이될 때 마지막 나누는 수가 최대 공약수가 된다.

ex)
1071과 1029의 최대공약수를 구하면 마지막 나머지가 0이되는 수 21이된다.

• 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어 떨어진다.

◇ 구현

1. 재귀함수 사용

public class test {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int GCD = gcd(n, m);
		int LCM = (n * m) / GCD;

		
		br.close();
        bw.write(Integer.toString(GCD));
        bw.newLine();
        bw.write(Integer.toString(LCM));
        bw.flush();
	}
	
	public static int gcd(int p, int q) {
		if (q == 0) return p;
		return gcd(q, p % q);
	}
}

※ 재귀함수에서 대소관계 구분이 필요없는 이유
ex) n = 12, m =18을 입력 할 경우

•  처음 gcd(12, 18)를 호출
•  gcd 함수는 두 인자 p와 q를 받음, 여기서 p = 12, q = 18
•  gcd 함수의 구현에서 q가 0이 될 때까지 재귀적으로 호출하며 최대공약수를 계산
•  현재의 호출에서는 q가 0이 아니므로, 재귀 호출로 gcd(q, p % q)를 수행
•  따라서 gcd(12, 18)은 gcd(18, 12 % 18)로 변화
•  여기서 12 % 18은 12
•  따라서 새로운 호출은 gcd(18, 12)
  
  

2. 일반적인 구현

public class test {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int B = n > m ? n : m;
		int S = n > m ? m : n;
		int tmp = 0;
		
		while(S != 0) {
			tmp = S;
			S = B % S;
			B = tmp;
		}
		
		int GCD = tmp;
		int LCM = (n * m) / GCD;

		
		br.close();
        bw.write(Integer.toString(GCD));
        bw.newLine();
        bw.write(Integer.toString(LCM));
        bw.flush();
	}
}