[java] 최대공약수 최소공배수 구하기

안녕하세요. 소다맛사탕 입니다.

오늘은 자바를 이용해 유클리드 호제법, 즉 최대공약수와 최소공배수를 구하는 알고리즘을 짜보았습니다.

 

※ 유클리드 호제법

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나.
호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타냄.

 

1. 일반적인 방법

public class Gcd_Test_01 {
	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();
		int min = (a < b) ? a : b;   // 참이면 a이고 아니면 b 인거지.
		int gcd = 0;
		for (int i = 1; i <= min; i++) {
			if (a % i == 0 && b % i == 0)
				gcd = i;
		}
		System.out.println("최대공약수 : " + gcd);
		System.out.println("최소공배수 : " + a * b / gcd);

	}
}

>> 두 수를 입력하세요.
>> 20
>> 30
>> 최대공약수 : 10
>> 최소공배수 : 60

삼항연산자를 이용해 값을 비교하고, 비교한 값을 이용해 최대공약수와 최소공배수를 뽑아낸다.

 

 

2. 생성자 이용 방법(method)

public class Gcd_test_02 {
	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);
	}
}

>> 두 수를 입력하시오.!
>> 20
>> 55
>> 최대공약수 = 5
>> 최소공배수 = 220

class 안에서 사용할 static 생성자(method)인 gcd를 이용하여, 두 값을 비교하여 리턴 시킵니다.

 

최대공약수와 최소공배수를 출력하는 방법이 여러가지 겠지만,

 

알고리즘을 짜는 방식이나 방법은 사람마다 다르기에

여러가지 방법이 생길 수 있다고 생각합니다.

포스팅을 봐주시는 모든 분들이 더 나은 방법을 찾아 알고리즘을 구현해 보는것을 추천드립니다.