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

public class WeirdNumbers {
	
	public static void main(String[] args) {
		
		final int max = 1000000;	// find weird numbers up to and including this
		final String fname = "weird1M.txt";	// and store them in this file
		
		TreeSet<Integer> factorSet=new TreeSet<Integer>();
		Set<Integer> semiperfSet = new HashSet<Integer>();
		int factorSum=1,abun,factor;
		
		try {
			PrintStream outFile=new PrintStream(new FileOutputStream(fname)); 
			long rt=System.currentTimeMillis();
			
			loop:for(int theNumber=2;theNumber<=max;theNumber+=2,factorSum=1) {
				factorSet.clear();
				for(int ii=2;ii<Math.sqrt(theNumber);ii++) {
					if(0==theNumber%ii) {
						// check if a factor of the number is within the set of stored semiperfect numbers
						if(semiperfSet.contains(ii)||semiperfSet.contains(factor=theNumber/ii)) continue loop;
						// if there is no such entry, store the new found factors and calculate new sum
						factorSet.add(ii); factorSet.add(factor);
						factorSum+=ii+factor;
					}
				}
				
				if((abun=factorSum-theNumber)<=0) continue;	// check if number is abundant
				if(factorSet.contains(abun)) {	// check if the abundance is within the set of factors
					semiperfSet.add(theNumber);	// store this semiperfect number for later checks 
					continue;	// and continue, since no semiperfect number can be weird.
				}
				factorSet.add(1);	// 1 is always a factor
				TreeSet<Integer> smallFactorSet = (TreeSet<Integer>)factorSet.subSet(1,abun);
				Integer smallFactorArr[] = smallFactorSet.toArray(new Integer[smallFactorSet.size()]);
				
				// check if any sum of factors < abun can be added up to abun
				if(backTrack(smallFactorArr,0,abun)) {
					semiperfSet.add(theNumber); // store this semiperfect number for later checks
					continue; // and continue, since no semiperfect number can be weird.
				}
				outFile.println(theNumber);	// found a weird number, put it into file
			}
			System.out.println((System.currentTimeMillis()-rt)+"ms");
			outFile.close();
		} catch(Exception e) { e.printStackTrace(); }
	}
	
	static boolean backTrack(Integer a[],int k,int n) {
		if(n>=a[k]) {
			if(0==(n-=a[k])) return true;
			if(k+1<a.length && backTrack(a,k+1,n)) return true;
			n+=a[k];
		}
		if(k+1<a.length && backTrack(a,k+1,n)) return true;
		return false;
	}
}