KINGBOB - Editorial

PROBLEM LINK:

Practice
Contest

Author: Varun Singh

DIFFICULTY:

CAKEWALK - SIMPLE

PREREQUISITES:

Math

PROBLEM:

Given a positive integer N, find the total number of factors of N.

QUICK EXPLANATION:

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.

EXPLANATION:

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 SOLUTIONS:

Author’s solution can be found here.