Euclidean algorithm(유클리드 호제법)

Euclidean Algorithm

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘의 하나이다.

 

2개의 자연수 a,b에서 a를 b로 나눈 나머지를 r이라고 했을때 GCD(a,b) = GCD(b, r)과 같게 되고 r이 0이 될때의 b의 값이 최대공약수가 된다.

 

일반적으로 쉽게 생각할 수 있는 최대공약수를 구하는 방법은 모든 자연수를 나눠보는 것이다.

하지만 이경우 시간복잡도는 O(n)이 된다.

 

다만 이 유클리드 호제법을 사용할 경우 O(logN)이 되어 더 빠른 속도를 나타낼 수 있다.

 

Greatest Common Divisor(GCD)

2개의 자연수의 공통된 약수인 공약수 중 가장 큰 공약수가 최대공약수이다.

소스코드

※ 아래 코드는 a>b 를 만족함을 가정

 

C++

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

JAVA

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

Least Common Multiple(LCM)

2개의 자연수의 공배수 중 가장 작은 수

소스코드

C++

int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

JAVA

 public static int lcm(int a, int n) {
	return p*q/gcd(a, b);
 }