Author: Varun Singh
CAKEWALK - SIMPLE
Given a positive integer N, find the total number of factors of N.
Loop till square root of the N, to count both factors in a single iteration. To take care of the corner case when N is a perfect square, increment the count only by 1.
Counting the factors of the given integer using Brute Force will result in TLE, so we will exploit an interesting property of numbers. For a number N, it can be factored into two factors a and b (in case of prime, 1 and N itself). One of both factors is always less than or equal to the square root of N and the other is always greater than or equal to the square root. If both a and b were greater than the square root of N, (a*b) would be greater than N.
So we run our loop only till square root of N, and if i completely divides N, then i and N/i, both are factors, hence we increase the count by 2. If N is a perfect square, i and N/i will be equal, so for this iteration, we only increase the counter by 1.
Author’s solution can be found here.