Two players take turns playing a number game starting with a positive integer n on the board. On each turn, the current player must choose a value x such that 0 < x < n and x divides the current value of n evenly, then replace n with n - x. A player who cannot make a legal move loses the game.
Player 1 moves first. Assuming both players play optimally, return true if Player 1 is guaranteed to win, and false otherwise.
Input
n: the starting positive integer on the board
Output
A boolean: true if Player 1 wins with optimal play, false otherwise.
Examples
Example 1
Inputn = 4
Outputtrue
Explanation: Player 1 picks 1 (n becomes 3), Player 2 picks 1 (n becomes 2), Player 1 picks 1 (n becomes 1), and Player 2 has no legal divisor move, so Player 1 wins.
Example 2
Inputn = 3
Outputfalse
Explanation: From n = 3 the only legal choice is x = 1, leaving n = 2 for Player 2, who picks 1 and forces Player 1 into n = 1 with no move.
Example 3
Inputn = 2
Outputtrue
Constraints
- 1 <= n
- Both players play optimally.