유클리드 호제법(최대공약수, 최소공배수)

이전에도 알고리즘 문제를 풀 때 최대공약수, 최소공배수를 구하는 문제가 많이 나왔다. c언어를 공부하던 중 또 나와서 글을 올리게 됬다.

우리는 수학과가 아니므로 증명을 할 필요는 없다(대수학에서 배웠다 나는 수학과라서..)

 

최대공약수

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

ㅣ

function gcd(n1, n2) {
  return n1%n2 ? gcd(n2, n1%n2) : n2;
}

 

최소공배수

a * b / gcd(a,b)