### 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

p^{v}

<=K.

we add ‘v’ to the answer for each prime.