We assume that the reader has basic knowledge of Combinatorial Game Theory (CGT). If not, a great introduction is an electronic text Ferguson: Game Theory (it can be downloaded from Thomas Ferguson's homepage).
How to decide which are the winning positions and which not? First of all, we should abbreviate this game. We can substract from each heap the nearest smaller prime. We can do this because once a prime is in reach, the player to move will reach it. (The best way to find the nearest prime is a plain linear search with O(sqrt N) primality testing, the primes are reasonably dense.)
Now we have another game. If you remove all matches from some heap, you win. If the size of some of the heaps is at most K then the player to move wins immediately after his first move.
If not, then making a heap this small means that you lose after the opponent's next move. In other words, the smallest "legal" heap size is K+1, nobody wants to make a smaller heap.
Now subtract K+1 from the size of each heap. Thereby we get a classical NIM game. The player with no move loses. (In the previous version of the game, he would be in a situation where all heaps have the size K+1, and thus he has to decrease one of them and lose in the next move.)
The NIM game has a known and simple stratege: a position is winning if and only if the bitwise xor of (heap size mod K+1) is non-zero.
Some more words about nasty special cases. The problem statement clearly stated that A player wins if after his move the size of some heap is a prime number.. What happens if there is a prime-sized heap in the beginning? If there is at least one other heap, the monkey wins by removing matches from the other heap – the size of the good heap remains prime. The remaining one-heap case is simple.