Edit (Nov 1, 2015): Bounty awarded, but the full question (i.e., what is the optimal strategy) remains open at the time of this update.
Consider the Factor Game played as follows:
Given a list of positive integers $1, \ldots, n$, two players (red and blue) alternate turns.
On each turn, the player picks and circles (in their color) any un-circled number $k$ that has at least one proper divisor yet to be circled; their opponent responds by circling (in their own color) all remaining proper divisors of $k$.
Then they switch (colors adjusted accordingly) and the game continues until there are no legal moves remaining.
At that point, each player adds up their circled numbers and the greater sum wins.
Question: What is the optimal strategy in the Factor Game?
My guess is that, for large enough $n$, picking the number that nets the most points on each individual turn is optimal. For example, if $n = 49$, then the first player would pick $47$ (to net $46$) and their opponent would respond with $49$ (to net $42$). But this strategy is admittedly short-sighted.
(Clearly the strategy fails for some small choices of $n$ (the example of $n = 4$ is provided in the comments; $n = 9$ is another failure) but I'm okay with assuming $n$ is sufficiently large.)
I am hoping for a description of an optimal strategy and a proof that it is optimal (for $n$ large enough), but would be interested in special cases, heuristic arguments for what would be an optimal strategy, and heuristic arguments for why this problem is difficult.
Motivation: This game is sometimes played in elementary schools (or, in my classes, with elementary school teachers) to explore concepts like prime, composite, divisor, proper divisor, etc. In such a case, the numbers are usually presented in an array – often a square array, and so my particular interest is when $n$ is a square.
You can play the Factor Game through the NCTM (National Council of Teachers of Mathematics) Illuminations site if you would like to experience it for yourself.
Here is a sample board when $n = 49$ (presented as a $7 \times 7$ array):
Best Answer
Clean-up on previous edits
The greedy strategy may be described, as stated in the OP, for large enough $n$, as locally optimal number-picking so as to net the most points on each individual turn.
This fails for $1\leq n\leq 500$ for the following $n:$
$$4, 9, 25, 28, 29, 42, 52, 53, 54, 58, 59, 60, 61, 66, 77, 86, 102, \ 103, 104, 108, 109, 114, 115, 117, 122, 123, 161, 162, 176, 177, 182, \ 183, 184, 185, 187, 189, 194, 195, 210, 211, 216, 217, 221, 228, 229, \ 238, 239, 243, 245, 247, 248, 249, 273, 282, 283, 286, 287, 288, 289, \ 292, 293, 298, 310, 311, 312, 313, 324, 325, 330, 331, 333, 338, 339, \ 343, 344, 345, 350, 351, 354, 355, 363, 364, 365, 369, 374, 375, 376, \ 382, 383, 384, 385, 387, 391, 392, 395, 396, 397, 405, 407, 408, 409, \ 412, 413, 414, 415, 420, 421, 429, 432, 433, 436, 437, 442, 443, 444, \ 445, 452, 453, 458, 466, 467, 477, 482, 487, 488$$
In these cases (where for the original "greedy strategy", one would pick the highest prime in the range to open the game), pick the highest odd semiprime in the range. From the opening choice onward, play the greedy strategy. This strategy results in a win for player $1$ for all $n\leq 500.$
With this approach, it is possible to avoid the "play low" game as described below, along with its obvious pitfalls.
Using the MMA code in the link below, one can find all opening numbers that give a win for player one (and thereafter playing as per local optimal strategy). Taking $n=25$, for example, which fails to give a win using the local optimal strategy,
gives $5, 7, 11, 25$ (hence, choose $25$ as the opening play since it is the largest odd semiprime in the given range) as the winning opening numbers for player $1$.
Likewise, testing the numbers that fail on the prime openings:
results in all positive values.
Original answer
Modifying the first choice to $2$ (as opposed to the largest prime in the range) where the "short-sighted" solution fails appears to be the winning strategy.
However, this does not hold for $n=77$:
strat[n]
for any $n\geq30$ should then force a win for player $1$ for most $n$. Note that player $2$ plays the local optimal strategy, but, though I would be surprised if an alternative strategy could force a win for player $2$, this possibility is yet to be explored.Note
Of course, since the game will be reversed if player $1$ chooses $1$ to start, and in so doing, allows player $2$ to go first, if player $2$ plays by the same strategy, he will choose $2$, etc., making the game rather absurd. A rule that either player may not forfeit a turn should then be adhered to, if a sensible solution is to be arrived at.
Added
I believe that the local strategy results in the longest game for large enough $n$. Interestingly, the length of the game for the local strategy for each $n\sim n/e:$
Mathematica code available here.