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

사진출처: 위키피디아

 

 

 

 

자연수 $N$의 약수를 구해보자.

먼저 $i=1,2,3,4\cdots \lfloor \sqrt{N}\rfloor$일 때, $N$을 $i$로 나눕니다. 만약 $Nmodi=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$$

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

이를 통해서 $\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;
}