[알고리즘] 약수 구하기 알고리즘

보통 가장 간단한 모든 약수를 구하는 알고리즘하면 1부터 N까지 반복문을 돌려 N % i == 0 일경우 약수로 하는 알고리즘을 생각할 것이다. 이경우 시간 복잡도는 O(N)이 되는데  O(√N) 으로 줄일 수있다.

 

방법은 간단하다. N의 약수들 중 √N 이하의 것들을 구하고 그 것들을 N에 나누면 다른 약수들도 구할 수있다.

 

예를 들어서 111의 약수를 구할 때  √110 이하의 약수들은 1, 2, 5, 10 이고 이 것들을 110에 나누면  11, 22, 55, 110 이 나온다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
vector<int> vec;
int main() {
	int n = 110;
    
    // sqrt를 안쓰고 i * i를 이용함
	for (int i = 1; i * i < n; i++) {
		if (n % i == 0) {
			vec.push_back(i);
			vec.push_back(n / i);
		}
	}
    // 정렬
	sort(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << endl;
	}
}

 

 

참고

https://bit.ly/3vq6VIH