There is an unknown number $x (1 \le x \le n)$. You have to guess that number. The only thing you are allowed is that you can ask question.
Is $x$ divisible by $y$? $[1 \le y \le n]$
What will be the minimum number of questions needed in order to guess the number correctly?
e.g. if $n = 4$,
you need to ask at least $3$ questions :
If $x$ is divisible by $2$?
If $x$ is divisible by $3$?
If $x$ is divisible by $4$?
Hence, if $x$ is not divisible by any number, it is $1$. If its divisible by $4$, $x=4$. If its divisible by $3$, $x=3$, else $x=2$.
Hence, the answer is $3$ questions needed. Can anyone please generalize it for $n$?
IMO, I need to at least test divisibility for all primes $\le n$. What else?
Example 2
For $n=6$, answer will be : $4$. You need to ask at least $4$ questions in the worst case to identify any number between $1$ and $6$. Hence, you will ask divisibility for $2,3,4,5$ to identify any number between $1$ and $6$.