ENIGMA01 - Editorial

ad-hoc
easy
editorial
engm2015
sieve

#1

PROBLEM LINK:

Guess the Number

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.

SOLUTION:

Link to Solution


#2

why Can’t he ask in the manner of binary search on v(prime power) ?