Data provided by Pastebin.com - Download Raw
import java.util.*;
import java.math.*;

public class PrimeCompositeGame {
        boolean [] primes;
        int [] dif;
   public int theOutcome(int N, int K) {
           if(N<3)return 0;
           sieve();//to get the primes
           difBuild();//to build all the differences between index and the closest smaller prime
           int l = firstlose(K);//get the first integer the difference between it and the closest smaller prime is bigger than K
           if(l==-1||l>N){// you win
                   return win(N,K);
           }else{//you lose
                   return lose(N,K);
           }
   }
   private int lose(int n,int k) {
           int turns=0;
           while(true){
                   if(dif[n]==0&&dif[n-1]>k-1)return -1*turns;//if you can't move
                   if(dif[n]>k)return -1*turns;//if you can't move
                   if(dif[n]==0)n--;//if you started at a prime
                   n=n-dif[n];//get the closest prime
                   for (int i = 1; i <= k; i++) {//search if there exist a losing state in range
                           if(n-i<0)continue;
                           if(dif[n-i]>k)return -1*(turns+2);
                   }
                   for (int i = 0; i < k; i++) {//get the smallest integer you can get
                           if(n-k+i<0)continue;
                           if(!primes[n-k+i]){n=n-k+i;break;}
                   }
                   turns+=2;
           }
}
private int win(int n,int k) {
        int turns=0;
        while(true){
                if(n-3<=k){//no more moves
                        return turns+1;
                }
                turns+=2;
                for (int i = 0; i < k; i++) {//get the smallest prime within range then remove one
                        if(n-k+i<0)continue;
                        if(primes[n-k+i]){n=n-k-1+i;break;}
                }
        }
}
private void sieve() {
        // TODO Auto-generated method stub
        primes=new boolean[500000];
        Arrays.fill(primes, true);
        primes[0]=false;
        primes[1]=false;
        for (int i = 2; i < primes.length; i++) {
                if(primes[2]){
                        for (int j = i+i; j < primes.length; j+=i) {
                                primes[j]=false;
                        }
                }
        }
   }

        private void difBuild(){
                dif=new int[500000];
                for (int i = 2; i < dif.length; i++) {
                        if(primes[i])dif[i]=0;
                        else dif[i]=dif[i-1]+1;
                }
        }
        private int firstlose(int k){
                for (int i = 4; i < dif.length; i++) {
                        if(dif[i]>k)return i;
                }
                return -1;
        }
}