[c++]최소 공배수와 최대 공약수 구하기

최소 공배수와 최대 공약수

최소 공배수와 최대 공약수를 구하라고 하면 중학생들이 아마 가장 잘 할 것이다. ಠ◡ಠ (인정?)

옛날에 학창시절에 배웠던 기억을 떠올리면 일단 두 수의 약수들을 구할 것이다. 예시를 보자. 

[3, 12]

3의 약수: 1,3
12의 약수: 1, 2, 3, 4, 6, 12

최소 공배수: 3 
최대 공약수: 12

 

물론, 고등학교 때 유클리드 호제법이라는 것을 배워 조금 더 수훨하게 구했을 것이다. 우리는 유클리드 호제법을 이용하여 코딩을 하는게 가장 합리적인 방법이겠징.

 

유클리드 호제법

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

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

 뭐든 위키백과를 먼저 보고 오는게 이해가 잘 될 것이다. 

유클리드 호제법 정리

 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘이다. 코드로 좀 더 간단히 보자 

int a,b,c;
c = a%b;

//a와 b의 최대공약수는 b와 c의 최대공약수와 같다.

 따라서, 이 과정들을 반복해 나머지가 0이 되었을 때 나누는 수가 a,b의 공약수라는 이야기이다. 음, 말로 하기 어렵고 수학으로 하기 어려우니 우리의 언어 c++로 설명해보겠다. 

최대공약수 

int EA(int a, int b){

	int c; 
    
    while(b != 0){
    	c = a%b;
        a = b;
        b = c;
    }
    
    // a를 return한다는 것을 잊지 말자. c=a 하고 c를 return해도 되고.
	return a;
}

너무너무너무 간단하지 않은가. 자 이렇게 되면 최소공배수는 뚝. 딱. 하고 만들어진다. ಠ◡ಠ  이번에는 최소공배수를 구해보자. 

최소공배수

최소공배수는 최대공약수를 구했다면 고등학교에서 배웠던 수식만 활용하여 쓰면 된다. 

최소공배수 = (두 수를 곱한 값)/ (두 수의 최대공약수)

int LCM(int a, int b){

	int c = (a*b)/EA(a,b);
    return c;
    
}

 너무너무 간단한 최소공배수, 최대공약수 구하기! 잊어버리지 말자. (｀▽´)