import java.util.Arrays;

/**
 * Created by on 25.04.16.
 */
class Task {
    public static void main(String[] args) {
        int[] primes= primes(1000000);
        long start = System.currentTimeMillis();
        for (int n = 6; n < 1000000; n++) {
            if(n%2==0) {
                search(n-2, primes, 2); // add 2 yourself after search completed
            } else {
                search(n, primes, 3);
            }
        }
        System.out.println("time = " + (System.currentTimeMillis()-start));
    }
    private static void search(int n, int[] numbers, int count) {
        search(n, numbers, count, numbers[numbers.length-1], new int[count]);
    }

    private static boolean search(int n, int[] numbers, int rem, int maxV, int[] state) {
        if(rem == 0)
            return false;
        int start = Arrays.binarySearch(numbers, n / rem);
        start = start>=0?start:-(start + 1);
        for (int i = start; i < numbers.length; i++) {
            int v1 = numbers[i];
            if(v1 > maxV) {
                break; // fail
            }
            if(v1*rem == n) {
                Arrays.fill(state, 0, rem, v1);
               // System.out.println(Arrays.stream(state).sum()+" = " + Arrays.toString(state));
                return true; // ok
            }
            state[rem-1] = v1; // if(v1*rem )
            if(search(n-v1, numbers, rem-1, v1, state)) {
                return true;
            }
        }
        return false;
    }

    private static int[] primes(int max) {
        int[] ps = new int[max];
        Arrays.parallelSetAll(ps, k -> k);
        for (int i = 2; i <= Math.sqrt(max); i++) {
            for (int j = i; i*j < max; j++) {
                ps[i*j] = 0;
            }
        }
        return Arrays.stream(ps).filter(v->v>1).toArray();
    }
}