Count Divisors

Given a positive integer N, find and return the total count of its divisors.

A divisor is any positive integer that divides N completely, leaving a remainder of 0.

Brute Force Approach

The first observation is very direct: every positive divisor of N must lie somewhere between 1 and N. So if the goal is to find all divisors, one simple way is to check every number in that range.

The next observation is that a number should be counted only when it divides N exactly. That means the remainder must be 0. Once this is noticed, the logic becomes straightforward: test each number from 1 to N and count the ones that leave no remainder.

Algorithm

• Start by keeping a variable named count as 0, because no divisor has been confirmed yet. This variable will store how many valid numbers have been found so far.

• Move through every number from 1 to N, because every positive divisor of N must lie in this range. No value outside this range can be a positive divisor of N.

• For each number i, check whether N % i == 0. This remainder check matters because only numbers that divide N exactly should be counted.

• Whenever the remainder becomes 0, increase count by 1. That step records the fact that one more valid divisor has been discovered.

• After all numbers have been tested, return count, because by then every possible positive divisor has either been accepted or rejected.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), because every number from 1 to N is checked.

Space Complexity: O(1), because only a few variables are used.

Optimal Approach

The smarter idea starts with a small pattern. When 2 divides 12, 6 also appears automatically. When 3 divides 12, 4 also appears. So divisors do not show up alone. They arrive in pairs.

That observation changes the whole approach. Instead of walking all the way to N, only the smaller side of each pair needs to be searched. Once a divisor i is found, its partner N / i is already known. This is why checking only up to sqrt(N) is enough. The only place where extra care is needed is a perfect square such as 36, because the pair becomes (6, 6), and the same divisor must not be counted twice.

Algorithm

• Start by keeping a variable count as 0, because the answer has not been built yet. This variable will collect the number of divisors as valid pairs are found.

• Check numbers starting from 1 while i * i <= N. This limit is important because anything larger than sqrt(N) would only repeat information that already comes from a smaller paired divisor.

• For every i, first test whether it divides N exactly. If it does not, there is no pair to count, so the process simply moves forward.

• If i divides N, then one divisor pair has been discovered. Usually that means two divisors should be added: i and N / i.

• Before adding 2, check whether i * i == N. If that happens, both values in the pair are actually the same number, so only 1 should be added. This protects the answer from double-counting the square root in perfect squares.

• After all possible smaller divisors have been tested, return count, because every valid divisor pair has already been covered.

Key Points

• For a perfect square like 36, the square root must be counted only once.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(sqrt(N)), because only numbers up to the square root are checked.

Space Complexity: O(1), because no extra data structure is needed.