Divisor Game
Two players take turns playing a number game. Starting with the number n on the board:
- The current player chooses a number
xwhere0 < x < nandxdividesnevenly - Replace
nwithn - x - The player who cannot make a move loses
Player 1 moves first. Both players play optimally, meaning each one picks a move that wins whenever such a move exists.
Input & Output
Input
n — the starting number on the board
Output
true if Player 1 wins with both players playing optimally, false otherwise
Example
Input
n = 2
Output
true
Explanation
Player 1 picks x = 1, leaving 1 on the board. Player 2 needs an x with 0 < x < 1, and none exists, so Player 2 loses.
Example
Input
n = 3
Output
false
Explanation
The only divisor of 3 below 3 is 1, so Player 1 must leave 2. Player 2 then plays x = 1 and leaves 1, which Player 1 cannot move from.
Constraints
1 <= n <= 1000