약수 구하기 최적화

백준 문제를 풀던 중 약수에 대해 공부할 기회가 생겨 찾아보던 중에 에라토스테네스의 채와 같이 제곱근의 형태를 띄는 최적화를 알게 되었다.

	for (int i = 1; i <= n; i++) {
		if (n % i == 0) cout << i << ' ';
	}

기본적인 약수 구하는 방법은 O(N)으로 구하려는 수가 i를 돌면서 나누어 떨어진다면 약수이다. 그러나 이 식으로는 21억같은 큰 수들은 꽤 오랜 시간이 걸린다.

이를 위해서 약수의 특성을 이용하여

	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) cout << i << ' ' << n / i << ' ';
	}

이런 식으로 하여금 구할 수 있다.

 

int 형 범위의 대푯값인 21억을 넣어서 확인해봤다.

시간복잡도O(N)

시간복잡도 O(N^1/2)

 

간단한 코드 차이지만 눈에 띄게 시간이 줄어든다. 

 

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	vector<int> ar;
	cin >> n;
	clock_t start = clock();
	//for (int i = 1; i <= n; i++) {
	//	if (n % i == 0) ar.push_back(i);
	//}
	//cout << endl;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) cout << i << ' ' << n / i << ' ';
	}
	cout << endl;

	sort(ar.begin(), ar.end());
	ar.erase(unique(ar.begin(), ar.end()), ar.end());
	for (int i = 0; i < ar.size(); i++) cout << ar[i] << ' ';
	cout << endl;

	clock_t end = clock();
	cout << "TIME: " << (end - start) / CLOCKS_PER_SEC << endl;

	return 0;
}

 

약수일 때마다 벡터에 푸쉬해주고 정렬한 뒤 중복되는 수를 제거해서 출력해줬다.