import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class SumOfDifferentPrimes { public static class SieveOfEratosthenes { private boolean[] a; public SieveOfEratosthenes(int N) { a = new boolean[N + 1]; for (int i = 0; i < N; i++) { a[i] = true; } a[0] = false; a[1] = false; int root = (int) Math.sqrt(N); for (int i = 2; i <= root; i++) { for (int j = 2 * i; j <= N; j += i) { a[j] = false; } } } public boolean isPrime(int n) { return a[n]; } public List<Integer> getPrimes() { List<Integer> list = new ArrayList<Integer>(); for (int i = 1; i < a.length; i++) { if (a[i]) { list.add(i); } } return list; } } public static void main(String[] args) throws FileNotFoundException { InputReader in = new InputReader(System.in); SieveOfEratosthenes soe = new SieveOfEratosthenes(1120); List<Integer> primes = soe.getPrimes(); int[][][] arr = new int[primes.size() + 1][1121][15]; arr[0][0][0] = 1; for (int i = 1; i < primes.size() + 1; i++) { int prime = primes.get(i - 1); for (int j = 0; j <= 1120; j++) { for (int k = 0; k <= 14; k++) { if ((j + prime) <= 1120 && k < 14) { arr[i][j + prime][k + 1] += arr[i - 1][j][k]; } arr[i][j][k] += arr[i - 1][j][k]; } } } while (true) { int n = in.nextInt(); int k = in.nextInt(); if (n == 0 && k == 0) break; if (n == 0 || k == 0) { System.out.println(0); continue; } System.out.println(arr[primes.size()][n][k]); } } public static class InputReader { private BufferedReader reader; private StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public long nextLong() { return Long.parseLong(next()); } public int nextInt() { return Integer.parseInt(next()); } } }
Sample Input:
24 3 24 2 2 1 1 1 4 2 18 3 17 1 17 3 17 4 100 5 1000 10 1120 14 0 0
Sample Output:
2 3 1 0 0 2 1 0 1 55 200102899 2079324314