Euler Problem 21

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.

First, use the factoring routine from Problem 12 and then the trick is to not double-up on numbers over the iteration.

import java.util.ArrayList;

public class Euler21
{
    public static void main(String[] args)
    {
        System.out.print(“Problem 21:\n”);
        Euler21 e = new Euler21();
        System.out.print(“Answer = ” + e.Problem()+ “\n”);
    }
    public String Problem ()
    {
        int sum = 0;
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        for (int a = 1; a <= 10000; a++)
        {
            int b = d(a);
            if (a == d(b) && a != b)
            {
                if (numbers.contains(a) == false)
                    numbers.add(a);
                if (numbers.contains(b) == false)
                    numbers.add(b);
            }
        }
        for (int n: numbers)
            sum += n;
        return String.valueOf(sum);
    }

    public int d (int num)
    {
        ArrayList<Integer> factors = new ArrayList<Integer>();
        int sum = 0;
        factors.add(1);
        for (int n = 2; n <= Math.ceil(Math.sqrt(num)); n++)
            if (num % n == 0 && factors.contains(n) == false)
            {
                factors.add(n);
                if (factors.contains(num/n) == false)
                    factors.add(num/n);
            }
        for (int n : factors)
            sum += n;
        return sum;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s