import java.util.*;

public class WeirdNumbers {
	public static void main(String[] args) {
		long[] time = {0,0};
		int rounds = 5;
		int prerun = 3;
		for (int i=0;i<(prerun+rounds)*2;i++) {
			long start = System.nanoTime();
			int round = i%2;
			if (round == 0) {
				numbersPlain();
			} else {
				numbersFor();
			}
			long end = System.nanoTime();
			if (i >= 2*prerun) {
				time[round] += end-start;
			}
		}
		System.out.printf("Plain:\t\t%5.8fs\nFor Loop:\t%5.8fs\n", time[0]/1000000000./rounds, time[1]/1000000000./rounds);
	}
	
	static boolean backTrack(int a[], int k, int n) {
		if(n == 0) return true;
		if(k == a.length) return false;
		if(n >= a[k]) {
			n -= a[k];
			if(backTrack(a,k+1,n)) return true;
			n += a[k];
		}
		if(backTrack(a,k+1,n)) return true;
		return false;
	}
	
	static void numbersPlain() {
		List<Integer> al=new ArrayList<Integer>();
		List<Integer> tl=new ArrayList<Integer>();
		
		List<Integer> rl=new ArrayList<Integer>();
		HashSet<Integer> spn = new HashSet<Integer>();
		
		int l=2,s=0,c=0,a,n; 
		
		outer:
		for(;;l+=2,s=1) {
			if(spn.contains(l)) continue;
			al.clear();
			for(int i=2;i<Math.sqrt(l);i++) {
				if(0==l%i) {
					if(spn.contains(i)||spn.contains(n=l/i)) {
						continue outer;
					}
					al.add(i); al.add(n);
					s+=i+n;
				}
			}
			if((a=s-l)<=0) continue;
			if(al.contains(a)) {
				spn.add(l); 
				spn.add(l*2);
				continue;
			}
			tl.clear();
			al.add(0,1);
			
			for(int i:al) if(i<a) tl.add(i);
			int ta[]=new int[tl.size()];
			for(int i=0;i<ta.length;i++) ta[i]=tl.get(i); 
			
			if(backTrack(ta, 0,a)) {
				spn.add(l); 
				spn.add(l*2);
				continue;
			}
			int na[]=new int[al.size()];
			for(int i=0;i<na.length;i++) na[i]=al.get(i); 
			
			if(!backTrack(na,0,l)) {
				rl.add(l);
				if(1000==++c) break;
			}
		}
	}
	
	static void numbersFor() {
		List<Integer> al=new ArrayList<Integer>();
		List<Integer> tl=new ArrayList<Integer>();
		
		List<Integer> rl=new ArrayList<Integer>();
		HashSet<Integer> spn = new HashSet<Integer>();
		
		int l=2,s=0,c=0,a,n; 
		
		outer:
		for(;;l+=2,s=1) {
			if(spn.contains(l)) continue;
			al.clear();
			for(int i=2;i<Math.sqrt(l);i++) {
				if(0==l%i) {
					if(spn.contains(i)||spn.contains(n=l/i)) {
						continue outer;
					}
					al.add(i); al.add(n);
					s+=i+n;
				}
			}
			if((a=s-l)<=0) continue;
			if(al.contains(a)) {
				for(int i=1;i<=2;i++) {
					spn.add(l*i);
				}
				continue;
			}
			tl.clear();
			al.add(0,1);
			
			for(int i:al) if(i<a) tl.add(i);
			int ta[]=new int[tl.size()];
			for(int i=0;i<ta.length;i++) ta[i]=tl.get(i); 
			
			if(backTrack(ta, 0,a)) {
				for(int i=1;i<=2;i++) {
					spn.add(l*i);
				}
				continue;
			}
			int na[]=new int[al.size()];
			for(int i=0;i<na.length;i++) na[i]=al.get(i); 
			
			if(!backTrack(na,0,l)) {
				rl.add(l);
				if(1000==++c) break;
			}
		}
	
	}
}