Factoring Algorithm puzzle
What is the minimal number, X, of yes/no questions needed to find the smallest positive integer divisor (other than 1) of an integer between 2 and 166 (inclusive)?
We are asking for the exact answer in two cases:
- In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions.
- On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.
This problem was IBM’s Ponder This puzzle of November 2009.
I’m going to write my solution in English, along with code (both python and java) so anyone knowing any one of the 3 languages should be able to follow along.