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

for (int i=0; i<f(N); i++)
    for (int j=0; j<f(N); j++)

이 알고리즘의 정확한 시간복잡도인지는 모르겠다.
하지만, O(root(N)^2) 보다 빠른 속도로 수행함은 보장할 수 있다.

이유를 생각해보자.
우선 약수의 개수를 구해보자.

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

즉 약수의 개수는 항상 2 * root(N) 이하의 값을 가진다.
따라서 다음이 성립한다.

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