If $A$ and $B$ are playing a game in which they have a number $n \geq 2$ and take turns dividing it with $p$ or $p^2$ for some prime $p \mid n$ such that whoever lands on $1$ after the series of divisions wins the whole game. If $A$ is given the start, find who has a better winning chance.
And, we can generalize the problem for $p$ or $p^2$, $\cdots$ or $p^k$ for some $k\leq n$ as well. How?
In this problem, it seems we have to do a backward approach. Like, the winner will be left with some prime $q$ or its square ($q^2$), which means, the loser was previously left with $qp$ or $q^2p$. How to proceed? Like, any hints?
I know that this is a variant of the Nim game. But when this problem is given, what's the intuition behind it? How would someone come up with that algorithm? (The winning strategy)