[Java]최대 공약수, 최소 공배수 구하기(feat.유클리드 호제법)

 

 안녕하세요 코북입니다. 오늘은 최대 공약수와 최소 공배수를 구하는 문제를 풀어봤습니다. 풀이가 다양하여 제가 푼 방식을 공유해보려고 합니다. 첫 번째 방식은 문제에 나와있는 것처럼 최대 공약수와 최소 공배수의 개념에 대해 파악한 후 문제에 접근했습니다.

 

최대 공약수란?

0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수이다. 따라서 두 정수 a와 b의 최대 공약수는 a의 약수인 동시에 b의 약수인 수, 즉 두 정수 a, b의 공약수 중에서 가장 큰 수를 의미한다.

 

여기서 '공통되는', '동시에'라는 특징이 나오기 때문에 &&를 사용하여 값을 구하려고 하였습니다.

 

"최소 공배수는 0이 아닌 두 개 이상의 정수의 양의 공배수 중에서 가장 작은 수이다."라고 나와 있지만, 최대 공약수를 활용하여 쉽게 구할 수 있습니다. 

 

public class Java07 {
	public static void main(String[] args) {
		
		System.out.println("최대 공약수 & 최소 공배수 구하기");
		System.out.print("숫자1입력 >> ");
		Scanner sc = new Scanner(System.in);
		int num1 = sc.nextInt();
		
		System.out.print("숫자2입력 >> ");
		int num2 = sc.nextInt();
		
		int max = 0; //최대 공약수
		
		for(int i=1; i<=num1 && i<=num2; i++) 
		{
			if(num1%i==0 && num2%i==0)
			{
				max = i;
			}
		}		
		
		int min = (num1*num2)/max; //최소 공배수

		System.out.println("최대 공약수 : " + max);		
		System.out.println("최소 공배수 : " + min);
	}
}

 

 

 두 번째 방법은 유클리드 호제법을 사용한 방법입니다. 두 수를 입력하면 유클리드 호제법에 의해 최대 공약수가 구해지는 메소드를 만들었습니다. 단, 유클리드 호제법은 a>b인 경우에만 만족하기 때문에 a가 b보다 작을 경우 두 수의 값을 바꿔주는 if문이 필요했습니다. 최소 공배수는 마찬가지로 최대 공약수와의 관계를 이용하여 구할 수 있습니다.

 

아 그리고, 유클리드 호제법은 가장 오래된 알고리즘 중 하나이기 때문에 구글에 검색하시면 쉽게 찾아볼 수 있습니다. 쉽게 찾을 수는 있지만 쉽게 이해가 되지는 않는 것 같습니다. 

public class Java07_2 {
	public static void main(String[] args) {
		
		System.out.println("최대 공약수 & 최소 공배수 구하기");
		Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
		int b = sc.nextInt();
				
		System.out.println("최대 공약수 : " + gdc(a, b));
		System.out.println("최소 공배수 : "+ lcm(a, b));
	}
	
	static int gdc(int a, int b) { //최대 공약수
		if(a<b) // 유클리드 호제법 조건
		{
			int temp = a;
			a = b;
			b = temp;
		}
		while(b!=0) { // 유클리드 호제법
			int r=a%b;
			a=b;
			b=r;
		}
		return a;
	}
	
	static int lcm(int a, int b) { //최소 공배수
		return a*b / gdc(a,b);
	}
}

 

배운 점

 최대 공약수와 최소 공배수를 구하는 과정에서 유클리드 호제법을 적용하여 문제를 해결해 볼 수 있었고, 메소드를 직접 만들어 적용하여 코드를 간결화시킬 수 있었다.

 

 

 

 

본 글은 아래 링크의 내용을 참고하여 학습한 내용을 나름대로 정리한 글임을 밝힙니다.

최소 공배수, 최대 공약수

https://terms.naver.com/entry.naver?docId=3338367&cid=47324&categoryId=47324

https://terms.naver.com/entry.naver?docId=3338368&cid=47324&categoryId=47324

유클리드 호제법

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95