Author and Editorialist : Kamini Pandey
Ad-hoc , Easy
Sieve of Eratosthenes
To guess what is minimum number of questions that are needed to be asked to correctly guess any number in the given range.
The idea is to get the number of primes factor for all the numbers up to K. Firstly lets compute number of primes <= K (This part can be pre computed using Sieve of Eratosthenes
). Then for every prime ‘p’ we need to find highest ‘v’ such that
we add ‘v’ to the answer for each prime.