Project Euler #23 in Java

john smith Published at Dev

John Smith

I've spent quite a while working on Problem #23 on Project Euler.

The answer the program below gives me is 4190428, and I can't figure out why.

I think it's probably a one or two character mistake somewhere.

public long problem23() {

    ArrayList<Integer> abundantNumbers = new ArrayList<Integer>();
    int limit = 28123;
    for(int i = 2; i < limit; i++) {
        if(isAbundantNum(i)) {
            abundantNumbers.add(i);
        }
    }

    boolean [] abundantSum = new boolean [limit+1];
    for(int a = 0; a < abundantNumbers.size(); a++) {
        for(int b = 1; b < abundantNumbers.size(); b++) {
            int temp = abundantNumbers.get(a) + abundantNumbers.get(b); 
            if(temp <= limit) {
                abundantSum[temp] = true;
            } else {
                break;
            }
        }
    }
    long sum = 0;
    for(int i = 1; i <= limit; i++) {
        if(!abundantSum[i]) {
            sum += i;
        }
    }
    return sum;
}

public boolean isAbundantNum(int n) {
    int factorSum = 1;
    for(int i = 2; i < Math.sqrt(n); i++) {
        if(n%i == 0) {
            factorSum += i; factorSum += n/i; 
        }
    }
    if(factorSum > n) {
        System.out.println(n);
        return true;
    }
    return false;
}

Edit: Added isAbundantNum(int n) method.

Ted Bigham

You have 2 bugs...

for(int b = 1; b < abundantNumbers.size(); b++) {

'b' should start at zero not 1

for(int i = 2; i < Math.sqrt(n); i++) {
    if(n%i == 0) {
        factorSum += i; factorSum += n/i; 
    }
}

Factoring like that gives you duplicates (like 2*2 = 4, you're getting both 2s).

Try something like:

    for(int i = 2; i < n; i++) {
        if(n%i == 0) {
            factorSum += i;
        }
    }

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at2021-02-6

Comments

0 comments

From Dev