Topcoder SRM 575 DIV 2 L2 TheNumberGameDivTwo

//Topcoder SRM 575 DIV 2 L2 TheNumberGameDivTwo

import java.util.*;
import java.math.*;

//rename the class name before submit
public class TheNumberGameDivTwo {
    public static void main(String[] args) {
        TheNumberGameDivTwo obj = new TheNumberGameDivTwo();
        System.out.println(
                obj.find(
                        128
                        ));
    }

    public String find(int n) {
        boolean[] prm = GetPrimeTable(1000);
        String[] winner = new String[1001];
        winner[1] = "Brus";
        for (int i = 2; i <= 1000; i++) {
            if (prm[i])
                winner[i] = "Brus";
            else {
                List<Integer> divs = GetDivisors(i);
                String cwin = "Brus";
                for (Integer div : divs) {
                    int rem = i - div;
                    if (winner[rem] == "Brus") {
                        cwin = "John";
                        break;
                    }
                }
                winner[i] = cwin;
            }
        }
        return winner[n];
    }

    private List<Integer> GetDivisors(int n) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                int j = n / i;
                list.add(i);
                if (j != i)
                    list.add(j);
            }
        }
        return list;
    }

    public static boolean[] GetPrimeTable(int maxNum) {
        boolean[] isPrime = new boolean[maxNum + 1];
        for (int i = 0; i < isPrime.length; i++) {
            isPrime[i] = true;
        }
        isPrime[0] = isPrime[1] = false;
        int sqrtMaxNum = (int) Math.sqrt(maxNum) + 1;
        for (int i = 2; i <= sqrtMaxNum; i++) {
            if (!isPrime[i])
                continue;
            int k = i * i;
            while (k <= maxNum) {
                isPrime[k] = false;
                k += i;
            }
        }
        return isPrime;
    }

}