[알고리즘] 약수 구하기

void FindDivisor(vector<int>& out, int num)
{
	for (int i = 1; i <= sqrt(num); i++)
	{
		if (num % i == 0)
		{
			out.push_back(i);
			if (num / i != i)
				out.push_back(num / i);
		}
	}
	sort(out.begin(), out.end(), greater<int>());
}

 

약수를 구할 때 for문을 수의 크기만큼 돌리는것보다 약수는 그 수의 제곱근보다 크지 않다는 수학적 성질을 이용하여 for문을 제곱근의 크기 전까지만 돌리는 것이 효율적이다.

 

제곱근의 크기까지 for문을 돌리면서 0으로 나누어 떨어지는 수를 결과 벡터인 out에 추가하고,

약수의 중복값을 빼고 추가하기 위해 num / i != i 인경우를 비교하여 num / i 값을 또 추가해준다.