fork download
copy 
  1. import java.util.Arrays;
  2.  
  3. /**
  4.  * Created by on 25.04.16.
  5.  */
  6. class Task {
  7.     public static void main(String[] args) {
  8.         int[] primes= primes(1000000);
  9.         long start = System.currentTimeMillis();
  10.         for (int n = 6; n < 1000000; n++) {
  11.             if(n%2==0) {
  12.                 search(n-2, primes, 2); // add 2 yourself after search completed
  13.             } else {
  14.                 search(n, primes, 3);
  15.             }
  16.         }
  17.         System.out.println("time = " + (System.currentTimeMillis()-start));
  18.     }
  19.     private static void search(int n, int[] numbers, int count) {
  20.         search(n, numbers, count, numbers[numbers.length-1], new int[count]);
  21.     }
  22.  
  23.     private static boolean search(int n, int[] numbers, int rem, int maxV, int[] state) {
  24.         if(rem == 0)
  25.             return false;
  26.         int start = Arrays.binarySearch(numbers, n / rem);
  27.         start = start>=0?start:-(start + 1);
  28.         for (int i = start; i < numbers.length; i++) {
  29.             int v1 = numbers[i];
  30.             if(v1 > maxV) {
  31.                 break; // fail
  32.             }
  33.             if(v1*rem == n) {
  34.                 Arrays.fill(state, 0, rem, v1);
  35.                // System.out.println(Arrays.stream(state).sum()+" = " + Arrays.toString(state));
  36.                 return true; // ok
  37.             }
  38.             state[rem-1] = v1; // if(v1*rem )
  39.             if(search(n-v1, numbers, rem-1, v1, state)) {
  40.                 return true;
  41.             }
  42.         }
  43.         return false;
  44.     }
  45.  
  46.     private static int[] primes(int max) {
  47.         int[] ps = new int[max];
  48.         Arrays.parallelSetAll(ps, k -> k);
  49.         for (int i = 2; i <= Math.sqrt(max); i++) {
  50.             for (int j = i; i*j < max; j++) {
  51.                 ps[i*j] = 0;
  52.             }
  53.         }
  54.         return Arrays.stream(ps).filter(v->v>1).toArray();
  55.     }
  56. }
  57.  
Success #stdin #stdout 1.76s 321792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
time = 1421
https://ideone.com/aLYGHD
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!