C++ 약수 구하기 방법: 완전 탐색과 O(sqrt(N)) 최적화

핵심 정리

약수는 정수 N을 나누어 나머지가 0이 되는 수입니다. 모든 수를 확인하는 완전 탐색은 이해하기 쉽지만 N까지 반복하고, 약수가 i와 N / i의 쌍으로 나타난다는 성질을 이용하면 제곱근까지만 확인해 탐색 범위를 줄일 수 있습니다.

• Divisors 방식은 1부터 N까지 각 수로 나누어 보므로 시간복잡도는 O(N)입니다.
• Divisors2는 i * i가 N 이하인 동안만 검사하고, 약수 i를 찾으면 짝인 N / i도 함께 추가하여 검사 횟수를 O(sqrt(N)) 범위로 줄입니다.
• N이 완전제곱수이면 가운데 약수에서 i와 N / i가 같습니다. 원문처럼 set<int>에 넣으면 이 중복을 자동으로 제거하면서 정렬된 결과를 얻습니다.
• 원문의 VI는 vector<int>와 같은 정수 벡터 별칭, FORE는 반복문 매크로로 쓰였다고 읽을 수 있습니다. 독립 실행 코드로 옮길 때에는 표준 컨테이너와 for 문으로 풀어 쓰면 됩니다.
• 예를 들어 N이 12이면 1, 2, 3을 확인하면서 12, 6, 4를 함께 얻습니다. N이 16이면 4와 16 / 4가 같아지는 지점에서 중복 처리 이유가 드러납니다.

아래 첫 함수는 가장 단순한 기준 구현이고, 둘째 함수는 약수의 대칭성을 사용한 개선 구현입니다. 결과의 중복 제거와 정렬까지 필요한지에 따라 set 또는 vector와 후처리를 선택할 수 있습니다.

약수구하기

 

 

//Naive
VI Divisors(int n)
{
	VI v;
	FORE(i, 1, n)
	{
		if (n%i == 0) v.push_back(i);
	}
	return v;
}

//대칭성을 활용하면 sqrt 복잡도에 구할 수 있다.
VI Divisors2(int n)
{
	set<int> v;
	for (int i = 1; i*i <= n; i++)
	{
		if (n%i == 0) 
		{
			v.insert(i);
			v.insert(n/i);
		}
	}
	return VI(v.begin(), v.end());
}