Taxman Programming Project: Problem Description

The Rules

We write down the numbers from 1 to n, and whenever the player takes a number the taxman takes all the numbers left that divide it (if there are no numbers left that divide it then the player is not allowed to take it). The object of the game is for the player to get as high a score as possible, which is calculated as the sum of all the numbers he has been able to take.

An Example

Let's illustrate the rules with a run of the game (with n = 10):

1 2 3 4 5 6 7 8 9 10: Player takes 9,  taxman takes 1, 3.
  2   4 5 6 7 8   10: Player takes 6,  taxman takes 2.
      4 5   7 8   10: Player takes 10, taxman takes 5.
      4     7 8     : Player takes 8,  taxman takes 4.
            7       : End of game, nothing more can be taken.

Taxman's score = 1 + 3 + 2 + 5 + 4 + 7 = 22.
Player's score = 9 + 6 + 10 + 8        = 33.

The Task

Write a program in Java that plays taxman well.

The Exact Specification

The program should begin by asking the user for n, where the game is to be played with all the numbers from 1 up to n.
Next the program should work out which numbers to take to achieve a good score.
Finally the program should inform the user of the chosen strategy and the score achieved, in some user-friendly way.

Note: The program should work in reasonable time for all values of n up to, say, fifty thousand. This means that it probably won't be able to achieve the best possible score for larger values of n, but the goal is only to produce a good score, not the best possible.