[C++, 약수를 구하는 알고리즘] 약수를 구하는 다양한 방법과 소인수분해

약수란?  : 자기 자신과 나누어 떨어지는 수

소인수 분해? : 합성수를 소수의 곱으로 나타내는 방법을 말한다. 

 

---

 

1. 가장 간단한 약수 알고리즘

void factor(int a) {
	if (a <= 0) {
		return;
	}

	for (int i = 1; i <= a; i++) {
		if (a % i == 0) {
			cout << a << "의 약수 : " << i << endl;
		}
	}
}

 

2. 1번보다 더욱 효율적인 알고리즘

void factor(int a) {
	if (a <= 0) {
		return;
	}

	for (int i = 1; i <= a / 2; i++) {
		if (a % i == 0) {
			cout << a << "의 약수 : " << i << endl;
		}
	}
    cout << a << "의 약수 : " << a << endl;
}

- 생각해보자, 왜 i <= a / 2 로 했을까? 왜 2로 나누었을까?

15의 약수를 구한다고 생각해보자. 15 / 2는 7이다(나머지는 버리므로) 15의 약수는 1, 3, 5, 15 이다. 15를 제외하면 모든 약수들은 절대 이 절반을 나눈 값보다 크지 않는다.

짝수인 24도 생각해보자. 24 / 2 는 12이며 24의 약수는 1, 2, 3, 4, 6, 12, 24 이다. 이 역시 24를 제외하면 모든 약수들은 절대 이 절반을 나눈 값보다 크지 않는다.

그렇지만 이 방법은 반복문에서 자기자신을 출력하는 부분은 없고 따로 출력을 해야 한다. 이보다 더 업그레이드 되는 것은 무엇이 있을까?

3. 2번의 내용 강화

void factor(int a) {
	if (a <= 0) {
		return;
	}

	for (int i = 1; i * i <= a; i++) {

		if (i * i == a) {
			cout << i << "는 " << a << "의 중복되는 제곱수 " << endl;
		}else if (a % i == 0) {
			cout << a << "의 약수 : " << i << ", "<< a / i << endl;
		}
	}
}

- 이 역시 15를 생각해보자. 15의 약수는 1, 3, 5, 15이다.

i를 1부터 시작하면 i * i = 1은 15를 넘지 않는다. 반복문 내용을 수행하고 i는 1이 증가되어서 2가 되었다.

i가 2가 되면, i * i = 4 역시 15를 넘지 않는다. i = 3일떄, 3 * 3 = 9역시 15를 넘지 않는다. 그러나 4 * 4 = 16은 15를 넘어서 여기서 사용되는 i는 1, 2, 3으로 총 3개이다.

2가 아닌 1과 3은 15와 나눠떨어지게 되는데, 보통 이때 나눠떨어지기 떄문에 자기자신과 해당 i를 나눈 값 또한 약수가 되기 때문에 성능이 1과 2에 비해서 훨씬 상승되는 것을 알 수 있다.

- 만약 16과 같은 제곱수가 있을 경우, 4는 16의 제곱수이므로 4가 2번 반복되어 출력될 수 있기 때문에 제곱수는 따로 뺴서 예외처리를 한다.

 

---

 

1. 소인수 분해

void prime_factor(int a) {
	cout << a << "의 소인수 분해 : ";
	for (int i = 2; i <= a; i++) {
		while (a % i == 0) {
			a /= i;
			cout << i << " ";
		}
	}
}

- 예를 들어 24를 소인수 분해 하면 2, 2, 2, 3이 나온다.

소인수 분해는 보통 1이 아닌 2부터 생각하기 때문에 반복문 for문을 사용하여 시작점을 2로 하고 a보다 작거나 같을 때 수행된다.

소인수 분해는 약수의 개념도 들어가있지만 약수와 달리 이 알고리즘은 약수를 찾고, 해당 수를 나눠떨어질 때까지 계속 약수와 나눠가며 갱신한다. 왜냐하면 소인수분해에서 요소는 약수밖에 되지 않기 때문이다.

 

 

---

** 보너스> C++로 구현하는 최대 공약수와 최소 공배수

1. 최대 공약수

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

int gcd2(int a, int b) {
	while (b != 0) {
		int temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}

2. 최소 공배수 - 간단하게 서로를 곱한 것에 최대 공약수를 나눠주면 된다.

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

- 예를 들어 20와 12의 최소 공배수를 구하고자 한다.

20의 소인수 분해는 2, 2, 5이며 12는 2, 2, 3이다.

여기서 최대 공약수는 2 * 2 이며 최소 공배수는 2 * 2 * 3 * 5이다.

20과 12를 곱해주면 2 ^ 4 * 3 * 5가 되는데 여기서 최소 공배수만 나눠주면 2 ^ 2 * 3 * 5가 된다.