Problem21

Problem 21
05 July 2002

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a  b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000

package com.yao;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by IntelliJ IDEA.
 * User: shuimuqinghua77
 * Date: 12-3-11
 * Time: 下午7:55
 */
public class Problem21 {

    public static void main(String[] args) {
         int top=10000;
         int  result=0;
        Set<Integer> invalid=new HashSet<Integer>();
        long start=System.currentTimeMillis();
         for(int i=2;i<top;i++){
             if(invalid.contains(i))
                 continue;
             int sum=sum(i);
             if(sum<=top&&sum!=i&&i==sum(sum)){
                 invalid.add(sum);
                 result+=(sum+i);
                 System.out.println("("+i+","+sum+")");
             }

         }
        long end=System.currentTimeMillis();
        System.out.println(end-start);
        System.out.println(result);
    }

    private static int sum(int n) {
        if(n==1)return 0;
        int sum=1;
        int middle=(int)Math.sqrt(n);
        for(int j=2;j<=middle;j++){
            if(n%j==0){
                 int k=n/j;
                if(k==j)
                  sum+=j;
                else
                    sum+=(k+j);
            }
        }
        return sum;
    }
}