1.Problem 21  
2.05 July 2002  
3.  
4.Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).  
5.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.  
6.  
7.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.  
8.  
9.Evaluate the sum of all the amicable numbers under 10000  

1.package com.yao;  
2.  
3.import java.util.HashSet;  
4.import java.util.Set;  
5.  
6./** 
7. * Created by IntelliJ IDEA. 
8. * User: shuimuqinghua77 
9. * Date: 12-3-11 
10. * Time: 下午7:55 
11. */  
12.public class Problem21 {  
13.  
14.    public static void main(String[] args) {  
15.         int top=10000;  
16.         int  result=0;  
17.        Set<Integer> invalid=new HashSet<Integer>();  
18.        long start=System.currentTimeMillis();  
19.         for(int i=2;i<top;i++){  
20.             if(invalid.contains(i))  
21.                 continue;  
22.             int sum=sum(i);  
23.             if(sum<=top&&sum!=i&&i==sum(sum)){  
24.                 invalid.add(sum);  
25.                 result+=(sum+i);  
26.                 System.out.println("("+i+","+sum+")");  
27.             }  
28.  
29.         }  
30.        long end=System.currentTimeMillis();  
31.        System.out.println(end-start);  
32.        System.out.println(result);  
33.    }  
34.  
35.    private static int sum(int n) {  
36.        if(n==1)return 0;  
37.        int sum=1;  
38.        int middle=(int)Math.sqrt(n);  
39.        for(int j=2;j<=middle;j++){  
40.            if(n%j==0){  
41.                 int k=n/j;  
42.                if(k==j)  
43.                  sum+=j;  
44.                else  
45.                    sum+=(k+j);  
46.            }  
47.        }  
48.        return sum;  
49.    }  
50.}