[java]유클리드 호제법을 이용한 최대공약수/최소공배수

오늘 프로그래머스 문제를 풀다가 이런 문제를 보았는데,

 

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

nmreturn

3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

최대 공약수와 최소공배수는 유클리드 호제법이라는것을 이용하면 쉽게 풀수 있다는 사실을 알아냈다.

 

1. 유클리드 호제법이란?

Euclidean Algorithm

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않는다(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다).[1] 일본의 수학 교육과정에서는 수학A로 다룬다. 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다.

유클리드 호제법

---

두 양의 정수 a,b\ (a>b)a,b (a>b)에 대하여 a=bq+r\,\left(0\le r<b\right)a=bq+r(0≤r<b)[2]라 하면, a,ba,b의 최대공약수는 b,rb,r의 최대공약수와 같다. 즉,

\gcd\left(a,\ b\right)=\gcd\left(b,\ r\right)gcd(a, b)=gcd(b, r)

r=0r=0이라면, a,ba,b의 최대공약수는 bb가 된다.

출처: 나무위키

 

2. 증명

gcd(a, b)=G, \gcd\left(b,\ r\right)=G'gcd(b, r)=G′이라 하자. 적당한 서로소인 정수 A,BA,B에 대해 a=GA,b=GBa=GA,b=GB가 성립한다. 이를 a=bq+ra=bq+r에 대입하면, GA=GBq+rGA=GBq+r이고, r=G\left(A-Bq\right)r=G(A−Bq)이다. 여기서 GG는 bb와 rr의 공약수임을 알 수 있다. 즉, GG는 G'G′의 약수이다.

G'=mGG′=mG로 두자. 그러면 적당한 서로소인 두 정수 k,lk,l에 대해 GB=G'k=Gmk, G(A-Bq)=G'l=GmlGB=G′k=Gmk,G(A−Bq)=G′l=Gml이 성립한다.
양변을 GG로 나누면 B=mk, A-Bq=mlB=mk,A−Bq=ml이다.
A=ml+Bq=ml+mkq=m\left(l+kq\right)A=ml+Bq=ml+mkq=m(l+kq)에서 mm은 AA와 BB의 공약수인데, gcd(A,B)=1gcd(A,B)=1이므로 항상 m=1m=1이고 G'=GG′=G이다.

 

a는 항상 b보다 크다는 가정을 가지고 코드로 짜보았더니,

public int eucd(int a,int b) //유클리드 호제법 (A>B
	{
		int r = a%b;
		if(r==0)
		{
			return b; 
		}
		else
		{
			return eucd(b,r);
		}
	}

와같이 생각보다 어렵지 않은 코드가 되었다. 처음에 증명하는 과정을 보았을때 이게 무슨소린가 싶었지만 막상 이해하고나니 생각보단 쉬웠다.

 

3. 문제풀이

이제 다시 본론으로 돌아가서 유클리드 호제법을 이용하여 최대공약수를 구한후, 최소 공배수를 구하는 방법은 최대공약수 * 두 숫자를 최대공약수로 나눈 몫이라는것을 보았다. 자세한것은 직접 소인수분해를 해서 증명해보면 된다.

이코드를 자바로 짜보았다.

package test_1;

import java.util.Scanner;

public class Solution
{
	Scanner Sc = new Scanner(System.in);
	public Solution()
	{
		int A = Sc.nextInt();
		int B = Sc.nextInt();
		
		int N = eucd(Math.max(A, B),Math.min(A, B));
		
		A=A/N; //최대공약수로 두수를 나눠서 몫구하는과정
		B=B/N;
		
		int M = A*B*N; //최소공배수는 최대공약수 * 두수의 몫
		
		System.out.println(N);
		System.out.println(M);
	}
	
	public int eucd(int a,int b) //유클리드 호제법 (A>B)
	{
		int r = a%b;
		if(r==0)
		{
			return b; 
		}
		else
		{
			return eucd(b,r);
		}
	}
}

위코드로 문제에 대입해보니 통과했다. 오늘도 하나 배웠다.