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(); }
}
aW1wb3J0IGphdmEudXRpbC5BcnJheXM7CgovKioKICogQ3JlYXRlZCBieSBvbiAyNS4wNC4xNi4KICovCmNsYXNzIFRhc2sgewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGludFtdIHByaW1lcz0gcHJpbWVzKDEwMDAwMDApOwogICAgICAgIGxvbmcgc3RhcnQgPSBTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMoKTsKICAgICAgICBmb3IgKGludCBuID0gNjsgbiA8IDEwMDAwMDA7IG4rKykgewogICAgICAgICAgICBpZihuJTI9PTApIHsKICAgICAgICAgICAgICAgIHNlYXJjaChuLTIsIHByaW1lcywgMik7IC8vIGFkZCAyIHlvdXJzZWxmIGFmdGVyIHNlYXJjaCBjb21wbGV0ZWQKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIHNlYXJjaChuLCBwcmltZXMsIDMpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigidGltZSA9ICIgKyAoU3lzdGVtLmN1cnJlbnRUaW1lTWlsbGlzKCktc3RhcnQpKTsKICAgIH0KICAgIHByaXZhdGUgc3RhdGljIHZvaWQgc2VhcmNoKGludCBuLCBpbnRbXSBudW1iZXJzLCBpbnQgY291bnQpIHsKICAgICAgICBzZWFyY2gobiwgbnVtYmVycywgY291bnQsIG51bWJlcnNbbnVtYmVycy5sZW5ndGgtMV0sIG5ldyBpbnRbY291bnRdKTsKICAgIH0KCiAgICBwcml2YXRlIHN0YXRpYyBib29sZWFuIHNlYXJjaChpbnQgbiwgaW50W10gbnVtYmVycywgaW50IHJlbSwgaW50IG1heFYsIGludFtdIHN0YXRlKSB7CiAgICAgICAgaWYocmVtID09IDApCiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICBpbnQgc3RhcnQgPSBBcnJheXMuYmluYXJ5U2VhcmNoKG51bWJlcnMsIG4gLyByZW0pOwogICAgICAgIHN0YXJ0ID0gc3RhcnQ+PTA/c3RhcnQ6LShzdGFydCArIDEpOwogICAgICAgIGZvciAoaW50IGkgPSBzdGFydDsgaSA8IG51bWJlcnMubGVuZ3RoOyBpKyspIHsKICAgICAgICAgICAgaW50IHYxID0gbnVtYmVyc1tpXTsKICAgICAgICAgICAgaWYodjEgPiBtYXhWKSB7CiAgICAgICAgICAgICAgICBicmVhazsgLy8gZmFpbAogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKHYxKnJlbSA9PSBuKSB7CiAgICAgICAgICAgICAgICBBcnJheXMuZmlsbChzdGF0ZSwgMCwgcmVtLCB2MSk7CiAgICAgICAgICAgICAgIC8vIFN5c3RlbS5vdXQucHJpbnRsbihBcnJheXMuc3RyZWFtKHN0YXRlKS5zdW0oKSsiID0gIiArIEFycmF5cy50b1N0cmluZyhzdGF0ZSkpOwogICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7IC8vIG9rCiAgICAgICAgICAgIH0KICAgICAgICAgICAgc3RhdGVbcmVtLTFdID0gdjE7IC8vIGlmKHYxKnJlbSApCiAgICAgICAgICAgIGlmKHNlYXJjaChuLXYxLCBudW1iZXJzLCByZW0tMSwgdjEsIHN0YXRlKSkgewogICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIGludFtdIHByaW1lcyhpbnQgbWF4KSB7CiAgICAgICAgaW50W10gcHMgPSBuZXcgaW50W21heF07CiAgICAgICAgQXJyYXlzLnBhcmFsbGVsU2V0QWxsKHBzLCBrIC0+IGspOwogICAgICAgIGZvciAoaW50IGkgPSAyOyBpIDw9IE1hdGguc3FydChtYXgpOyBpKyspIHsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IGk7IGkqaiA8IG1heDsgaisrKSB7CiAgICAgICAgICAgICAgICBwc1tpKmpdID0gMDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gQXJyYXlzLnN0cmVhbShwcykuZmlsdGVyKHYtPnY+MSkudG9BcnJheSgpOwogICAgfQp9Cg==