This is the Program that determines the winner in the Alice and Bob Subtraction Game. With the use of files the performance could be significantly increased.

Alice and Bob Subtraction Game

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Scanner;
import java.util.Set;





public class MainGame {

	public static void main(String[] args) throws Exception {
		//declaring variable to hold the number given to Alice
		int number;
		//declaring variable to hold the number of numbers given to Alice
		int numberOfTestCases;
		
		//creating a scanner to scan inputs from the console
		Scanner sc = new Scanner(System.in);
		System.out.println("Please enter the number of test cases for which you want to find out the winner");
		numberOfTestCases = sc.nextInt();
		System.out.println("Please enter the number that is given to Alice at the beginning");
		
		//Looping over all the inputs
		for(int i = 0;i < numberOfTestCases;i++){
			if(sc.hasNext()){
				number = sc.nextInt();
			
				if(number > 10000)
					System.out.println("Alice and Bob are still playing... Please wait for the result");
				String result = GetResults.generateResults(number);
				
				//Printing results of the game
				if(result.equals("same"))
					System.out.println("ALICE WINS THE GAME!!");
				else if(result.equals("other"))
					System.out.println("BOB WINS THE GAME!!");
				else System.out.println(result);
				
				if(i < numberOfTestCases-1)			
					System.out.println("Please enter the number that is given to Alice at the beginning");

			}

			
		}
		if(sc != null)
			sc.close();
		
	}
	

}
class PrimeNumbersAndGCDClass {
	//Retrieving the value of A
	public static int getA(int n){
		int count = 0;
		for(int i = 2;i < n;i++){
			if(isPrime(i)){
				if(isGcdCheckForA(i,n))
					count++;
			} 
		}
		
		return count;
	}
	//Retrieving the value of B
	public static int getB(int n){
		int count = 0;
		for(int i = 1;i <= n;i++){
			if(gcdCondForB(i,n) == 1){
				count++;
			}
		}
		
		return count;
	}
	//Checking if a number is prime
	static boolean isPrime(int n){
		if(n == 2 || n == 3)
			return true;
		else{
			for(int i = 2;i <= Math.sqrt(n);i++){
				if(n % i == 0)
					return false;
			}
			return true;
		}
	}
	//Validating for all the primes <= number whether the gcd(prime,number) = prime
	private static boolean isGcdCheckForA(int primeNum,int number){
		if(number%primeNum == 0)
			return true;
		else return false;
	}
	//Validating whether number i <= mainNumber is a co-prime of it
	private static int gcdCondForB(int mainNumber,int num){
		if(num == 0)
			return mainNumber;
		return gcdCondForB(num,mainNumber%num);
		
	}
}

class GetResults{
	
	private static LinkedHashMap<Integer,String> numberResults = null;
	public GetResults(){
	}
	//Allows for creation of only one object of the linkedHashMap<Integer,String> and reuses the same object for subsequent operations
	public static LinkedHashMap<Integer,String> getInstance(){
		if(numberResults == null){
			numberResults = new LinkedHashMap<Integer, String>();
			return numberResults;
		}
		else return numberResults;
		
	}
	
	//Checks if the number passed is already present in the linkedHashMap. 
	private static boolean isPresentInAllResults(int number,LinkedHashMap<Integer,String> allresults){
		if(allresults.size()==0)
			return false;
		if(number > allresults.size())
			return false;
		
		//Retrieving all the keys into an array to perform binary search of the elements
		Set<Integer> keys = allresults.keySet();
		Integer[] keyArr = new Integer[keys.size()];
		keys.toArray(keyArr);
		if(Arrays.binarySearch(keyArr, 0, keyArr.length-1, number) >= 0)
			return true;
		else return false;
	}
	
	//Determining the winner of the game
	public static String generateResults (int number){
		LinkedHashMap<Integer,String> allResults = GetResults.getInstance();
		
		if(PrimeNumbersAndGCDClass.isPrime(number))
			return "BOB WINS THE GAME!!";
		else if(isPresentInAllResults(number,allResults))return allResults.get(number);
		
		else{
	
			for(int i = allResults.size()+10;i <= number;i++){
				//If a prime number is initially given to ALice then Bob is definitely the winner
				if(i%2!=0 && PrimeNumbersAndGCDClass.isPrime(i)){
					allResults = GetResults.getInstance();
					allResults.put(i, "Other");
				}
				else{
					//Generating the values of A and B
					int valueOfA = PrimeNumbersAndGCDClass.getA(i);
					int valueOfB = PrimeNumbersAndGCDClass.getB(i);
					int nA;
					int nB;
					nA = i-valueOfA;
					nB = i-valueOfB;
					
					//Checking whether the person who gets the number wins the game or not
					if(nA < 10 && nB < 10)
						allResults.put(i, "other");
					else if(nA < 10){
						if(allResults.get(nB).equals("same"))
							allResults.put(i, "other");
						else allResults.put(i, "same");
					}
					else if(nB < 10){
						if(allResults.get(nA).equals("same"))
							allResults.put(i, "other");
						else allResults.put(i, "same");
					}
					else{
						if(allResults.get(nA).equals("same") && allResults.get(nB).equals("same"))
							allResults.put(i, "other");
						else allResults.put(i, "same");
					}
				}
			}
			return allResults.get(number);
		}
	}
}