최대공약수와 최소공배수 구하는 알고리즘 만들기

두수 a,b 와 a를 b로 나눈 나머지를 r이라고 하자. 

a와 b의 최대공약수는 b와 r의 최대 공약수와 같음을 이용하자. 

 

방법 1.  재귀함수를 사용하는 방법 

static int GCD(int a, int b){ // 최대공약수
	if (a%b == 0) {
		return b;
	}
	return GCD(b, a % b);
}

package Algorithm;

import java.util.Scanner;

public class Gcd {
	static int a, b;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("두 수를 입력하시오.!");
		a = sc.nextInt();
		b = sc.nextInt();

		if(b > a) {
			int temp = b;
			b = a;
			a = temp;
		}
		int result = gcd(a, b);
		System.out.println("최대공약수 = " + result);
		System.out.println("최소공배수 = " + a * b / result);
	}

	public static int gcd(int a, int b) {
		if (a % b == 0) {
			return b;
		}
		return gcd(b, a % b);
	}

}

해설 ) 

더큰수를 a에 담고 작은수를 b에 담는다. 이때 a%b ==0 이면 a를 b로 나눌수있는것 즉 b가 a의 약수이므로 최대공약수는 a가 된다. 

 

만약 나뉘지 않는 경우는  다시 gcd(b,a%b)를 리턴한다. 즉 다시 gcd를 리턴함으로써gcd(b,a%b)에 대하여 다시 최대공약수를 구하는 방법을 반복한다. 

 

또한  a  x b = 최대공약수 x 최소공배수 임을 이용하여 최소 공배수를 간단히 구할 수 있다. 

 

두 수가 서로소인 경우에는

예를들어 gcd(7,5)라고 하면 나누어떨어지지 않음으로 return gcd(5,2) 

하지만 또 나누어 떨어지지 않음으로 return gcd(2,1)

그러면 2와 1은 나누어 떨어지므로 1을 리턴하게 된다. 

이런식으로 계속 돌려서 리턴값을 찾는 것이다. 

 

방법2. 유클리드 호제법을 사용하는 방법 

두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘이다.

a>b일때 

static int gcd(int a, int b){ // 최대공약수
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

두수 a,b 와 a를 b로 나눈 나머지를 r이라고 하자. 

a와 b의 최대공약수는 b와 r의 최대 공약수와 같음을 이용하자. 

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