Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Java

Posted by Diego Murray
Diego Murray
2,515 Points

Project Euler Problem 21 - Amicable Pairs - JAVA

PROBLEM:

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.

QUESTION: My code never seems to stop running. Not sure why. Any recommendations on how to make my code run faster?

MY CODE:

package euler21;

public class amicableNumbers {

    public static final int top = 10000;

    public static void main(String[] args) {

        long startTime = System.currentTimeMillis();

        int sum = 0;
        for (int i = 220; i <= top; i++) {
            if(hasAmicablePair(i)) {
                sum += i;
            }
        }
        System.out.println(sum);

        long endTime = System.currentTimeMillis();
        System.out.println("Time: " + (endTime - startTime)/1000 );
    }

    public static boolean hasAmicablePair(int n1) {
        for (int i = 0; i <= top; i++) {
            if(sumOfDivisors(i) == n1) {
                return true;
            } 
        }
        return false;
    }

    public static int sumOfDivisors(int n2) {
        int tempSum = 0;
        for (int i = 1; i <= n2 / 2; i++) {
            if(n2 % i == 0) {
                tempSum += i;
            }
        }
        return tempSum;
    }
}

1 Answer

Seth Kroger
Seth Kroger
56,416 Points 
   // where you have ...
    public static boolean hasAmicablePair(int n1) {
        for (int i = 0; i <= top; i++) {
            if(sumOfDivisors(i) == n1) {
                return true;
            } 
        }
        return false;
    }
// ...perhaps instead...
    public static boolean hasAmicablePair(int n1) {
        int n2 = sumOfDivisors(n1);
        if (n1 == n2) {
           return false;  // covers the a != b condition
        }

        return n1 == sumOfDivisors(n2);
    }
Diego Murray
Diego Murray
2,515 Points

Thanks Seth!