Two players play a game and the rules are as follows:
$N$ wooden pieces (marked with numbers from $1$ to $N$) are placed in a bottle. A player takes out some piece, say "$x$", from the bottle, and then also takes out "all pieces numbered by divisors of $x$". Play continues in alternating fashion until one piece (last piece) remains in the bottle. The player who picks the last piece wins the game.
If both players play optimally, then, for a given $N$ and given player who starts the game, who wins the game ?
I worked out eight-to-ten examples and believe the answer to be
Whoever starts the game always wins, regardless of $N$.
I am interested in the proof or intuition of the answer.
Can someone please help?