Problem based on Prime numbers.

Problem based on Prime numbers.

Past codechef problem (Solutions are public)
Zach and Cody are playing a game. There are initially N chips on a table.
Zach starts the game making the first move. In each turn one has to choose
a move from a set of moves. The set of moves consists of all the moves of
removing pk chips from the table, where p is any prime and k is any non
negative integer. The winner is the one to take the last chip. Can you
decide who will win the game, assuming both the players follow a perfect
strategy? If Zach wins, what will be the smallest possible number that he
can remove in his first move?
i have a very week idea for it's solution which is divisibility by 6 after
having look at many solutions but i need a conceptual explanation. Please
provide that to get this concept.
solution is if there are n chips then
if(n%6==0)
Cody wins
else
Zach wins the game and can choose minimum n%6 chips in his first
move.
again sorry for poor English.