PROBLEM LINK:
Author and Editorialist : Kamini Pandey
DIFFICULTY:
Ad-hoc , Easy
PREREQUISITES:
Sieve of Eratosthenes
PROBLEM:
To guess what is minimum number of questions that are needed to be asked to correctly guess any number in the given range.
EXPLANATION:
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
pv
<=K.
we add ‘v’ to the answer for each prime.