유클리드 호제법(Java)

 

 

 

유클리드 호제법은

  Euclidean Algorithm 은 두 개의 수에서 최대공약수를 구하는 알고리즘이다.

최대공약수를 간단하게 말하자면 두 수 사이의 소인수들의 곱이 최대공약수이다. 우리가 흔히 수기로 최대공약수를 구할 때 소인수분해를 프로그래밍 코드 작성하면 시간 복잡도가 매우 큰 프로그램이 될 것이다. 그 이유는 간단하다. 소인수분해를 하기 위해 소수를 찾아야 하고 그 소수가 두 개의 수에 공통적으로 나눌 수 있는지 여부를 확인해야 하기 때문이다. 

 

  코딩으로 최대공약수를 구한다면 시간 복잡도를 줄이기 위해 유클리드 호제법을 사용한다. 

 

  유클리드 호제법은 아주 간단하다. 예로 바로 들자면   정수 A = 24 정수 B = 18  두 수의 최대 공약수를 유클리드 호제법으로 구한다고 치자.

 

1. 24%18 = 6  나머지 값이 0이 아니면 계속 실행
2. 18%6 = 0 18을 6으로 나누었을 때 나머지가 0이 나왔으므로 종료 두 수의 최대 공약수는 6이다. 

 

 

 

 

 

---

 

 

 

 

 

CASE1: (반복문 사용):

package pack;

import java.util.Scanner;

public class Main2 {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int inputNumberOne = sc.nextInt();
		int inputNumberTwo = sc.nextInt();
		System.out.println(GCD(Math.max(inputNumberOne, inputNumberTwo), Math.min(inputNumberOne, inputNumberTwo)));
	}

	static int GCD(int bigNumber, int smallNumber) {
		
		while (smallNumber!=0) {
			int num = bigNumber%smallNumber;
			
			bigNumber = smallNumber;
			smallNumber = num;
		}
		
		return bigNumber;
	}
}

변형

static int GCD(int bigNumber, int smallNumber) {
		int num = 0;
		while (true) {
			num = bigNumber%smallNumber;
			bigNumber = smallNumber;
			smallNumber = num;
			
			if(smallNumber==0) break;
		}
		return bigNumber;
}

 

 

 

CASE2: (재귀 사용):

package pack;

import java.util.Scanner;

public class Main2 {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int inputNumberOne = sc.nextInt();
		int inputNumberTwo = sc.nextInt();
		System.out.println(GCD(Math.max(inputNumberOne, inputNumberTwo), Math.min(inputNumberOne, inputNumberTwo)));
	}

	static int GCD(int bigNumber, int smallNumber) {
		int N = bigNumber % smallNumber;
		if (N == 0)
			return smallNumber;
		else
			return GCD(smallNumber, N); // 재귀호출
	}
}

 

 

 

 

 

 

최소공배수

System.out.println(inputNumberOne*inputNumberTwo/d);  //최소공배수
System.out.println((inputNumberOne/d)*(inputNumberTwo/d)*d);  //최소공배수

 

 

 

 

 

결과:

 

 

 

 

 

 

 

 

 

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

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

 

 

 

대표사진

https://www.flaticon.com/kr/free-icon/algorithms_1753819

<a href="https://www.flaticon.com/kr/free-icons/" title="연산 아이콘">연산 아이콘  제작자: Flat Icons - Flaticon</a>