Sane's Monthly Algorithms Challenge: November 2008

For this challenge, things are a little different. You are playing a game against Sane himself!

The game goes like so, starting with a positive integer ~n~, and a ~\text{score} = 0~.

1. I input the integer ~n~.
2. The game ends here if ~n = 1~.
3. You respond by outputting two positive integers which multiply to ~n~.
   This step increases your ~\text{score}~ by ~1~.
4. I choose one of the numbers you outputted. Let this number be ~n~.
5. Repeat from step ~1~.

The objective of the game is to maximize your ~\text{score}~.
You may assume that I am trying my hardest to minimize your ~\text{score}~ with step ~4~.

Input Specification

Every line will be a legal integer ~n~ ~(1 \le n \le 2\,000\,000\,000)~, according to the rules of the game. I will stop inputting numbers as soon as I enter 1.

Output Specification

Every line will be two integers, separated by a space.
Remember to end each line with a newline character.
You should flush the output buffer after each line (fflush(NULL) in C/C++, flush(output) in PAS).

Optimal Sample Interaction (Correct)

>>> denotes your output. Do not print this out.

32
>>> 4 8
4
>>> 2 2
2
>>> 2 1
1

This obtains a score of ~3~ (which is the maximum).

Suboptimal Sample Interaction (Incorrect)

32
>>> 2 16
2
>>> 2 1
1

This obtains a score of ~2~ (this is not the maximum).

Grading

For each interaction where you obtain the maximum possible score, you will have passed that piece of test data. If you ever make an illegal move, or get a lower score than the best possible, you will have failed that piece of test data.

Hints

Make sure you can prove to yourself that your strategy is, in fact, optimal.
Remember that I know how to make the best choice (especially in the long run) at step ~4~.