(UVA) Sum of Different Primes - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3654


The solution below used the concept of Knapsack, related to Dynamic Programming, to solve this problem.


import java.io.*;
import java.util.*;

class Main {
    public ArrayList<Integer> primes;
    public int[][][] matrix;
    public int differentNumbers;
    public int count;
   
    public int knapsack(int volume, int index, int numUsed) {
        if (volume == 0 && numUsed == differentNumbers) {
            return 1; // found one more possibility
        }
        else if (volume < 0 || index < 0 || numUsed > differentNumbers) {
            return 0;
        }
       
        if (matrix[volume][index][numUsed] >= 0) {
            return matrix[volume][index][numUsed];
        }
       
        int use = knapsack(volume-primes.get(index), index-1, numUsed+1);
        int notUse = knapsack(volume, index-1, numUsed);
        matrix[volume][index][numUsed] = (use+notUse);
        return matrix[volume][index][numUsed];
    }
   
    public void prime(int number) {
        for (int i = 2; i <= number; i++) {
            boolean prime = true;
            for (int j = i-1; j >= 2; j--) {
                if (i%j == 0) {
                    prime = false;
                    break;
                }
            }
            if (prime) {
                primes.add(i);
            }
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int number = sc.nextInt();
        differentNumbers = sc.nextInt();
        while (number != 0 || differentNumbers != 0) {
            primes = new ArrayList<>();
            prime(number);

            count = 0;
            matrix = new int[number+1][primes.size()][differentNumbers+1];
            for (int i = 0; i < number+1; i++) {
                for (int j = 0; j < primes.size(); j++) {
                    for (int k = 0; k <= differentNumbers; k++) {
                        matrix[i][j][k] = -1;
                    }
                }
            }
            bw.write(knapsack(number, primes.size()-1, 0)+"\n");
           
            number = sc.nextInt();
            differentNumbers = sc.nextInt();
        }
               
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}