Problem Link - Counting Divisors - I in Number theory
Problem Statement:
Given a positive integer N, the objective is to return the count of divisors of the number N including the number 1 and the number N itself.
For example, if x=18, the correct answer is 6 because its divisors are 1,2,3,6,9,18.
Note that we want to also count factors which aren’t prime.
Approach:
The approach to counting divisors of a number n is based on the fact that divisors come in pairs. For every divisor i of n, there exists a corresponding divisor \frac{n}{i} . By iterating only up to \sqrt{n} , we efficiently find all divisors, as any divisor greater than \sqrt{n} would have already been paired with a divisor smaller than \sqrt{n} .
- Check for divisibility: For each number i from 1 to \sqrt{n} , if i divides n evenly, then:
- i is a divisor.
- \frac{n}{i} is also a divisor unless i is the square root of n, in which case it only gets counted once.
- Count divisors: If i is a divisor, add both i and \frac{n}{i} to the divisor count, unless they are the same.
Complexity:
- Time Complexity: O(\sqrt{N} ) We are iterating from
1to \sqrt{n} , which takes \sqrt{n} iterations. - Space Complexity: O(1) No extra space needed.