1. 
package acm_10419_sum_up_the_primes;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_10419_sum_up_the_primes
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44&page=show_problem&problem=1360
*
* @author Martin Lambeck
* @version 1.0, 10.08.2010
*
* Method : precalculation, greedy?
* Status : Accepted
* Runtime: 2.380
*/

import java.util.Scanner;

public class Main
{

/*
primes < 300:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293
*/

//in lexicographic order
static int[] lprime = new int[]{
101, 103, 107, 109, 11, 113, 127, 13, 131, 137, 139, 149, 151, 157, 163, 167, 17, 173, 179, 181, 19, 191, 193, 197, 199, 2, 211, 223, 227, 229, 23, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 29, 293, 3, 31, 37, 41, 43, 47, 5, 53, 59, 61, 67, 7, 71, 73, 79, 83, 89, 97
};

static final int pcount = lprime.length;


// num[t][n][i] saves optimal solution
// t = number of summands
// n = sum
// i = number of occurrence of the prime of lexicographic index i (possible values = 0/1/2)
// for given t, n:
// num[t][n][pcount] > 0 if there is a solution,
// such that: SUM(num[t][n][i]) == t FOR i = [0; pcount[
// and such that: SUM(lprime[num[t][n][i]] * num[t][n][i]) == n FOR i = [0; pcount[
static int[][][] num = new int[15][1001][pcount+1];

static final int INDEX_OF_TWO = 25;

static Scanner sc = new Scanner(System.in);
static int tcase = 0;
static int n, t;

public static void main(String... args)
{
init();
while (testcase());
}

public static void init()
{
//double start = System.currentTimeMillis();

//trivial cases: sum with 1 summand
for (int i = 0; i < pcount; i++)
{
num[1][lprime[i]][INDEX_OF_TWO] = 1; //avoid that 2 is used twice
num[1][lprime[i]][i] += 1; //set use of prime to 1, or 2 in case of prime=2
num[1][lprime[i]][pcount] = 1; //a solutions was found
}

//calculate cases where 2 <= t <= 14
for (int i = 2; i <= 14; i++)
work(i);

for (int l = 1; l <= 14; l++)
for (int s = 1; s <= 1000; s++)
if (num[l][s][pcount] > 0)
num[l][s][INDEX_OF_TWO]--; //reduce the use of 2, so it contains the actual count of 2's now

//System.out.println("init time: " + (System.currentTimeMillis() - start ) / 1000.0);
}

public static boolean testcase()
{
n = sc.nextInt();
t = sc.nextInt();

if (n == 0 && t == 0)
return false;

System.out.printf("CASE %d:%n", ++tcase);

if (num[t][n][pcount] == 0)
{
System.out.print("No Solution.\n");

} else
{
boolean first = true; //dont print a + sign before the 1. summand

for (int i = 0; i < pcount; i++)
{
if (num[t][n][i] > 0)
{
if (num[t][n][i] == 2)
System.out.printf("%1$s%2$d+%2$d", (first ? "" : "+"), lprime[i]);
else
System.out.printf("%s%d", (first ? "" : "+"), lprime[i]);

first = false;
}
}

System.out.println();
}

return true;
}

public static void work(int l)
{
for (int i = 0; i < pcount; i++)
{
for (int j = 1; j < 1001; j++)
{
int psum = lprime[i] + j;

if (psum > 1000)
continue;

//if there is a solution to N=p, t=l-1
//and prime with index i is used at most once
if ((num[l-1][j][pcount] > 0) && (num[l-1][j][i] < 2))
{
num[l-1][j][i]++; //TEMPORARILY increase count, so array doesnt need to be copied for comparsion


//update if first solution, or solution is lexicograhic smaller than old solution
if ((num[l][psum][pcount] == 0) || isSmaller(num[l][psum], num[l-1][j]))
{
for (int h = 0; h < pcount; h++)
num[l][psum][h] = num[l-1][j][h]; //copy occurrences of primes
}

num[l][psum][pcount]++; //increase number of solutions

num[l-1][j][i]--; //undo the temporarily made change
}
}
}
}

//return true if the lexicographic order of nu, is smaller than the lexicographic order of old
public static boolean isSmaller(int[] old, int[] nu)
{
for (int i = 0; i < pcount; i++)
{
if (old[i] == nu[i])
continue;

if (old[i] > nu[i])
return false;

if (old[i] < nu[i])
return true;
}
return false; //same
}

}