I have the following problem:

How many divisors does a given number n have?

For example: n = 6 so the answer is 4 because we have 1, 2, 3, 6.

Naive method

You can loop through 1 to n, and count the divisors.

void countDivisors(int n) {
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(n % i == 0) {
            cnt++;
        } 
    }
    cout << cnt << endl;
}

The time complexity of this method is

$$O(n)$$

Improve the naive method

You can observe that if a * b = n and we know a and n, we can find b.

This leads us to this code

void countDivisors(int n) {
    int cnt = 0;
    for(int i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            cnt++;
            // Remember that, if we can only count 1 if a == b
            if(i != n / i) cnt++;
        }
    }
    cout << cnt << endl;
}

The time complexity of this method is:

$$O(\sqrt(n))$$

Prime factorization

I have an integer n and prime factorization of is

$$a^{x} b^{y} c^{z}$$

then I have this formula for counting divisors:

$$(x+1)(y+1)(z+1)$$

With this formula, we can apply Sieve to find the least prime factor up to n.

// Depend on the limit that we change the size
// Of the vector
vector<int> sieve(1000001, 1);

void sieve(int n) {
    for(int i = 2; i <= n; i++)
        pf[i] = i;

    for(int i = 4; i <= n; i += 2)
        pf[i] = 2;

    for(int i = 3; i * i <= n; i++) {
        if(pf[i] == i) {
            for(int j = i * i; j <= n; j += i) {
                if(pf[j] == j) {
                    pf[j] = i;
                }
            }
        }
    }
}

void factor(int n) {
    int res = 1;
    unordered_map<int, int> mp;
    while(sieve[n] != 1) {
        mp[sieve[n]]++;
        n /= sieve[n];
    }
    for(auto &p: mp) {
        res *= (p.second + 1);
    }

    cout << res << endl;
}

The time complexity of this method is

$$O(\log_n)$$

Additional Resources

https://mathschallenge.net/library/number/number_of_divisors

Problem practices

https://cses.fi/problemset/task/1713/ (Recommend)

https://www.spoj.com/problems/NUMDIV/