PROBLEM LINK:
Author: Kaushambi Gujral
Tester: Shivani Srivastava
Editorialist: Kaushambi Gujral
DIFFICULTY:
EASY
PREREQUISITES:
Number Theory
PROBLEM:
In a given range, we need to compute the numbers with odd number of factors.
QUICK EXPLANATION:
Only perfect squares have odd number of factors.
EXPLANATION:
G is the number of factors. Only if G is odd, will the value of f(G) be even, because-
f(G)=G+ k ; where k is an odd number
(odd + odd = even)
Thus, the number of factors must be odd.
As input, we are given the upper value of the range ‘X’. Each range begins with 1. We are required to print all the numbers in this range which have odd number of factors. Let us take some examples.
If X=6, then the values in this range are: 1, 2, 3, 4, 5, 6
Value No.of factors
1 1 (1)
2 2 (1,2)
3 2 (1,3)
4 3 (1,2,3)
5 2 (1,5)
6 4 (1,2,3,6)
Most people, who have understood this working, will follow brute-force by counting the number of factors of each number and checking if it’s odd or not. That would result in T.L.E. So, there must be a trick to solve this faster!
It should be noted that only perfect squares have odd number of factors. (Interesting, isn’t it!). The question, thus, reduces to a function which would only print perfect squares within the given range. Hence, if-
X=12, the output will be
1 4 9
X=28, the output will be
1 4 9 16 25
And so on.
AUTHOR’S AND TESTER’S SOLUTIONS:
The solution can be found here