약수 개수 시간복잡도 계산 팁

for (int i=0; i
이유를 생각해보자. 우선 약수의 개수를 구해보자.

N의 약수를 구할 때, 1부터 root(N)까지 나누면서, N이 나눠진다면, 나누는 수와 그 몫을 저장하면 된다. (두 개씩 저장한다) 즉 약수의 개수는 항상 2 * root(N) 이하의 값을 가진다.

따라서 다음이 성립한다. 이제 2*root(N)을 알고리즘에 대입한다면, 다음이 성립함을 알 수 있다....