Problem with non abundant sums

Hey everyone, I'm working on Project Euler problem 23 right now, which asks to find the sum of all numbers that can't be expressed as the sum of two abundant numbers: http://projecteuler.net/problem=23

I wrote this solution, but I'm getting 4179595 as the output instead of the expected 4179871, I'm sure it's probably a dumb error, but I can't see it. Also I was hoping someone could tell me what I could do to make it faster, since right now it takes it almost 20 seconds to run, most of it is the sort function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;       
using std::endl;
using std::vector;

bool is_abundant(const int& n){
    int sum = 0;

    if(n < 12)
        return false;

    for(int i = 1; i < (n / 2 + 1); ++i){

        if(n % i == 0)
            sum += i;

    }

    return sum > n ? true : false;
}

int main(){
    int sum = 0;
    vector < int > abu_nums, abu_sums;
    typedef vector < int >::const_iterator int_iter;

    for(int i = 0; i < 28123; ++i){

        if(is_abundant(i))
            abu_nums.push_back(i);

    }

    for(int_iter iter = abu_nums.begin(); iter != abu_nums.end(); ++iter){

        for(int_iter sub_iter = abu_nums.begin(); sub_iter != abu_nums.end(); ++sub_iter)
            abu_sums.push_back(*iter + *sub_iter);

    }

    sort(abu_sums.begin(), abu_sums.end());

    for(int i = 24; i < 28123; ++i){

        if(!binary_search(abu_sums.begin(), abu_sums.end(), i))
            sum += i;

    }

    cout << sum << endl;

    return 0;
}
Last edited on
I'm not sure why you're answer is incorrect. Anyway, you can get a speed boost by only checking divisors up to sqrt(n). I also used an array instead of vector in my solution, which is faster.
Topic archived. No new replies allowed.