최대공약수, 최소공배수, 소인수분해

 

1. 소인수분해

소수를 모두 구해서 나눠보는 것 보단 2부터 차례대로 나눠 나머지를 확인하는 것이 더 효율적이다.

왜냐하면 결국 2, 3, 5 등의 소수로 나눠떨어지지 않는다면 그들의 배수인 4, 6, 10.. 등으로도 나눠떨어지지 않을 것이기 때문에 항상 나누는 수가 소수일 때 먼저 나눠떨어지는 효과를 갖기 때문이다.

 

예를 들어, 24라는 수를 소인수분해하려면 우선 2로 나눠본다.

24 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 12를 다시 2로 나눈다.

12 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 6을 다시 2로 나눈다.

6 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 3을 다시 2로 나눈다.

3 % 2 = 1 나눠떨어지지 않으므로 3으로 다시 나눈다.

3 % 3 = 0 나눠떨어졌고 몫이 1이므로 종료한다.

24부터 1이 되기 까지 2, 2, 2, 3이 사용되었기 때문에 24 =2x2x2x3으로 나타낼 수 있다.

 

코드로 나타내면 아래와 같다.

#include <vector>

using namespace std;

vector <int> nums;

void factorization(int num) {
	int k = 2;
  while (num != 1) {
    if (num % k == 0) {
      num /= k;
      nums.push_back(k);
      k = 2;
    }
    
    else k++;
  }
}

 

 

2. GCD (최대공약수)

임의의 두 자연수 A, B의 최대공약수를 구하는 방법은 유클리드 알고리즘이 대표적이다.

 

유클리드 알고리즘

• A, B중 둘중 큰 값이 A라고 가정해보겠습니다.
• A를 B로 나눈 나머지를 R이라고 하면 (A%B = R)
• R이 0일때, B가 최대 공약수(GCD)입니다.
• 만약 B이 0이 아니라면, A에 B값을 다시 넣고 B를 B에 대입 한 후 R == 0이 될때까지 반복합니다.

 

1. 반복문을 이용한 최대공약수 구하기

int GCD (int A, int B) {
  if (A < B) swap(A, B);
  
  int R;
  while (B != 0) {
    R = A%B;
    A = B;
    B = R;
  }
  
  // B == 0이 됬으니까 A는 B가 0이 되기 이전 값을 가지고 있을 것이다.
  return A;
}

 

2. 재귀를 통한 최대공약수 구하기

int GCD (int A, int B) {
  if (B == 0) return A;
  else return GCD(B, A%B);
}

 

 

3. LCM (최소공배수)

임의의 두 수 A, B와 두 수의 최대공약수 G가 주어졌을 때, 최소공배수는 쉽게 구할 수 있습니다.

 

$$ A = G * \frac{A}{G} \\ B = G * \frac{B}{G} \\ $$

 

 

따라서 $$ LCM = G * \frac{A}{G} * \frac{B}{G}= \frac{A*B}{G} $$ 입니다.

int LCM (int A, int B) {
  return A*B/GCD(A, B);
}