[백준/BOJ] 13226번 Divisors (C/C++)

백준 온라인 저지(BOJ) 13226번 Divisors

https://www.acmicpc.net/problem/13226

13226번: Divisors Again

* 사용언어 : C언어, C++

 

1. 문제

최대 10개의 Test Case 에 대해서

주어지는 숫자 n 의 약수의 개수를 출력

 

2. 풀이

(1) full 탐색

1부터 n까지 탐색하면서 0 으로 나누어 떨어지면

그 수를 약수로 보고 count 를 늘리면 됩니다.

 

n 이 최대 10000 으로 매우 작기 때문에

전체 탐색을 해도 구동시간 문제 없이 정답이 됩니다.

int getDivisorsCount(int n) {
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		if (n % i == 0) ++cnt;
	}
	return cnt;
}

 

(2) 루트 n 까지 탐색

좀 더 빠르게 구현할 수 없을까 싶어서 구글링을 해보니

루트 n 까지만 탐색해도 되는 방법이 있어서 해당 코드로 구현을 해봤습니다.

 

n 이 p 로 나누어 떨어지면

p 가 n 의 약수임과 동시에 n / p 도 n 의 약수가 됩니다.

따라서 p 를 발견할 때마다 2 씩 더해주면 됩니다.

(ex. 12 의 약수인 3을 생각해보면, 12 / 3 = 4 도 12 의 약수)

 

이 방법은 1부터 n 까지가 아닌 루트 n 까지 탐색하면 됩니다.

마지막에 루트 n 이 약수가 된다면 1개를 추가해주어야 합니다.

(ex. 4 의 약수는 1, 2, 4)

int getDivisorsCount(int n) {
	int cnt = 0, i = 1;
	for (; i * i < n; ++i) {
		if (n % i == 0) cnt += 2;
	}
	if (i * i == n) ++cnt;
	return cnt;
}

 

(3) 소인수분해

120 을 소인수분해하면 2^3 * 3^1 * 5^1 로 표현할 수 있습니다.

소인수들의 지수를 활용해서 약수의 개수를 구할 수 있습니다.

 -> (3 + 1) * (1 + 1) * (1 + 1) = 16개

 

이 공식은 각 소인수가 포함되는 개수를 경우의 수로 따져보면 쉽게 이해가 됩니다.

120 의 약수는 2가 0, 1, 2, 3개로 총 4가지 경우, 3이 0, 1개로 2가지 경우, 5가 0, 1개로 2가지 경우라서

가능한 모든 경우의 수, 즉 약수의 개수는 4 * 2 * 2 = 16 개가 됩니다.

 

위 개념을 활용하여 n을 소인수분해 하면서 약수의 개수를 구했습니다.

 

이 방식은 n 을 나누면서 탐색 범위가 급격하게 줄어들기 때문에

위 2개 방식과 비교할 수 없을 정도로 빠릅니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
13225_Divisors
1112KB	0ms
*/
#include <cstdio>

int getDivisorsCount(int n) {
	int cnt = 1, p = 2, a;
	while (1) {
		a = 1;
		while (n % p == 0) {
			n /= p;
			++a;
		}
		cnt *= a;
		++p;

		if (n == 1) return cnt;
		else if (n < p * p) return cnt * 2;
	}
	return cnt;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int c, n;
	scanf("%d", &c);

	while (c--) {
		scanf("%d", &n);
		printf("%d %d\n", n, getDivisorsCount(n));
	}
	return 0;
}