검사 범위 최소화하여 약수 구하기

사진출처: 위키피디아

 

 

 

 

자연수 \(N\)의 약수를 구해보자.

먼저 \(i=1,2,3,4\cdots\left \lfloor \sqrt N \right \rfloor\)일 때, \(N\)을 \(i\)로 나눕니다. 만약 \(N\;mod\;i = 0\) 이라면 \(i\)는 \(N\)의 약수.
$$i\;|\;N$$
\(i\)가 약수라면 \(N/i\)도 약수입니다. 
$$\frac{N}{i}\;|\;N$$
그 이유는 \(N\)의 약수들은 항상 쌍으로 존재하기 때문입니다. 예를 들어 \(12\)가 \(3\)로 나누어 떨어지면 \(3\)도 \(12\)의 약수이고, \(\frac{12}{3}\)도 \(N\)의 약수입니다. 이 두 약수는 곱해서 \(12\)이 됩니다.
$$
i\times \frac{N}{i} = N
$$

범위가 \(\left \lfloor \sqrt N \right \rfloor\)까지인 이유는 약수의 쌍 중 한 숫자는 항상 \(\sqrt N\) 이하이고, 다른 숫자는 \(\sqrt N\) 이상이기 때문입니다. \(i\leq\sqrt N\)이면 \(\frac{N}{i}\geq\sqrt N\)입니다.  
예를 들어서 \(N=16\)이고 \(i=2\)이면 \(2\leq\sqrt 16\), \(\frac{16}{2}\geq\sqrt 16\)입니다.

이를 통해서 \(\sqrt N\)까지만 약수를 검사해도 되는 이유를 이해할 수 있습니다. 만약 \(\sqrt N\)을 넘는 약수가 있다면, 그 약수의 쌍은 반드시 \(\sqrt N\) 이하의 값이 됩니다. 따라서 \(\sqrt N\)까지만 검사해도 모든 약수를 찾을 수 있습니다.

 

다음은 위 내용을 C언어로 구현한 코드입니다 . 이 알고리즘의 시간 복잡도는 \(O\left(\sqrt N\right)\)입니다.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 비교 함수 (오름차순 정렬)
int compare(const void *a, const void *b)
{
	return (*(int *)a - *(int *)b);
}

int *find_divisors(int n)
{
	int *divisors = (int *)malloc(sizeof(int) * n);
	int index = 0;
	int limit = sqrt(n);

	for (int i = 1; i <= limit; i++)
	{
		if (n % i == 0)
		{
			divisors[index++] = i;
			if (n / i != i)
				divisors[index++] = n / i;
		}
	}

	qsort(divisors, index, sizeof(int), compare);

	return divisors;
}