[c++] 최대 공약수와 최소 공배수, N개 수의 최소 공배수

1. 최소 공배수 구하기 (LCM)

<최대 공배수를 구하는 방법>
12와 18의 최소 공배수를 구해보자.
12=6x2
18=6x3
12의 2와 18의 3이 서로소 이기 때문에 최소 공배수는
공약수 x 서로소= 6x2x3=36 이다.

그럼 최소 공배수를 각 두수를 이용해서 식을 나타낼 수 있다.
12 x 18 = 6x2x6x3인데,
6x2x3이 최소 공배수 이기 때문에
12x18=6x최소 공배수 이다. 이때 6은 두 수의 최대 공약수이다!
그렇다면, 최소 공배수= 각 두 수의 곱/최대 공약수로 나타낼 수 있다.

2. 최대 공약수(GCD)

그러면 최대 공약수는 어떻게 구할 수 있을까?
12와 18의 최대 공약수를 구해보자
최대 공약수는 두 수가 0으로 나누어 떨어질 때 최대 공약수라고 할 수 있다.
18과 12는 큰 수를 작은 수로 나누었을 때 0으로 나누어 떨어지지 않는다.
=> 18%12!=0
큰수: 18, 작은 수: 12 인데,

이때 두 수를 나누고 나머지를 다시 비교하게된다.
18%12==6
큰수: 12, 작은 수:6 이다.

이러면, 두 수는 0으로 나누어 떨어진다. (12%6==0)
그러면 작은수 6이 두 수의 최대 공약수이다.

이를 코드로 작성해보자.

int gcd(int a, int b){
	int MAX=max(a, b);
    int MIN=min(a, b);
    while (a%b!=0){
    	int remain= a%b;
        MAX=MIN;
        MIN=remain;
    }
    return MIN;
}

3. N개 수들의 최소 공배수

2개의 최소 공배수는 1번에서 구해보았다.

최소 공배수= 두 수의 곱/ 두 수의 최대 공약수

그럼 N개의 수들의 최소 공배수는 어떻게 구할까?
이또한 2개씩 비교하는 것이다.
arr=[2,4,5,8]; 이라면
2와 4의 최소 공배수 = 4;
4와 5의 최소 공배수 = 20;
20과 8의 최소 공배수= 40;
순서가 바뀌어도 상관없다.

그렇다면 코드로 구해보자.

int gcd(int a, int b){
	int MAX=max(a, b);
    int MIN=min(a, b);
    while (a%b!=0){
    	int remain= a%b;
        MAX=MIN;
        MIN=remain;
    }
    return MIN;
}

int main(){
	vector<int> arr ={2,4,5,8};
    
    int now=arr[0];
    for (int i=1; i<arr.size(); i++){	
        now=now * arr[i] / gcd(now, arr[i]);
    }
    
    return now;

}