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; }}