import java.util.ArrayList;
/**
* @author Umang
*/
/**
* 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.
*/
public class Problem21
{
private static boolean isAmicable(int no)
{
long sum = sum(getEvenDivisors(no));
long no2 = sum(getEvenDivisors(sum));
return no == no2 && sum != no;
}
private static long sum(ArrayList<Long> numbers)
{
long ans = 0;
for (Long number : numbers)
{
ans += number;
}
return ans;
}
private static ArrayList<Long> getEvenDivisors(long n)
{
long root = Math.round(Math.sqrt(n)) + 1;
ArrayList<Long> test = new ArrayList<Long>();
test.add(1L);
for (long i = 2; i <= root; i++)
{
if (n % i == 0)
{
test.add(i);
test.add(n / i);
}
}
return test;
}
public static void main(String[] args)
{
long sum = 0;
for (int i = 0; i < 10000; i++)
{
if (isAmicable(i))
{
sum = sum + i;
}
}
System.out.println("Sum = " + sum);
}
}
|
No comments:
Post a Comment