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