UVa 10419 - Sum-up the Primes

// UVa 10419 - Sum-up the Primes

import java.util.*;
import java.util.stream.Collectors;

public class Main {

    private static final List<Integer> LEXICOGRAPHICALLY_SORTED_PRIMES = lexicographicallySortedPrimes();
    private static List<Integer> P;
    private static int t, n;
    private static boolean[][] canGet;
    private static int[][] lastIndex;

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        for (int testCaseNumber = 1; true; testCaseNumber++) {
            n = scanner.nextInt();
            t = scanner.nextInt();
            if (n == 0 || t == 0) break;

            P = new ArrayList<>();
            for (Integer p : LEXICOGRAPHICALLY_SORTED_PRIMES) {
                if (p <= n) {
                    P.add(p);
                    if (p != 2)
                        P.add(p);
                }
            }

            canGet = new boolean[t + 1][n + 1];
            canGet[0][0] = true;
            lastIndex = new int[t + 1][n + 1];

            rec(0, 0, 0);

            System.out.printf("CASE %d:\n", testCaseNumber);
            if (canGet[t][n]) {
                int[] sol = new int[t + 1];
                int m = n;
                for (int a = t; a > 0; a--) {
                    sol[a] = P.get(lastIndex[a][m]);
                    m -= sol[a];
                }
                StringBuilder sb = new StringBuilder();
                sb.append(sol[1]);
                for (int a = 2; a <= t; a++) {
                    sb.append('+');
                    sb.append(sol[a]);
                }
                System.out.println(sb.toString());
            } else {
                System.out.println("No Solution.");
            }
        }
    }

    private static void rec(int a, int m, int z) {
        for (int pi = z; pi < P.size(); pi++) {
            int p = P.get(pi);

            int aa = a + 1;
            int mm = m + p;
            int zz = pi + 1;
            if (aa <= t && mm <= n && (!canGet[aa][mm] || pi < lastIndex[aa][mm])) {
                canGet[aa][mm] = true;
                lastIndex[aa][mm] = pi;
                if (canGet[t][n]) return;
                rec(aa, mm, zz);
                if (canGet[t][n]) return;
            }
        }
    }

    private static class Prime {
        final int p;
        final String s;

        Prime(int p) {
            this.p = p;
            this.s = String.valueOf(p);
        }
    }

    private static List<Integer> lexicographicallySortedPrimes() {
        boolean[] isComposite = new boolean[300];
        List<Prime> primes = new ArrayList<>();
        for (int i = 2; i < 300; i++) {
            if (!isComposite[i]) {
                for (int j = i * i; j < 300; j += i) {
                    isComposite[j] = true;
                }
                primes.add(new Prime(i));
            }
        }
        primes.sort(Comparator.comparing(a -> a.s));
        return primes.stream().map(a -> a.p).collect(Collectors.toList());
    }

}