What is the optimal strategy in the "Factor Game"?
Solution 1:
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,
With[{nn = 25},
Select[Transpose@{Range[2,nn],c4R[s1,nn,#] &/@ Range[2, nn]}, #[[2]] > 0&]]
%[[All, 1]]
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:
With[{nn = #}, c4R[s1, nn, Max@Select[Range@nn, OddQ@# == True &&
PrimeOmega@# == 2 &]]] & /@ {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}
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$:
Select[With[{aa = Select[Transpose@{Range@200, aa}, #[[2]] < 0 &]
[[All, 1]]}, Transpose@{aa, (Sign@bb)[[#]] & /@ aa}], #[[2]] < 0 &][[All, 1]]
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:$
dd = {0, 0, 0, 0}~Join~(Length@s4[s1, #, Max@Select[Range@#, PrimeQ]] & /@
Range[5, 200]); ListLinePlot[{dd, Range@200/E}]
Mathematica code available here.