sum of all abundant numbers less than or equal to n

Question

The problem is to find the sum of all abundant numbers less than or equal to n where an abundant number is a number whose sum of all proper factors is greater than that number for eg. 12 is an abundant number as
1 + 2 + 3 + 4 + 6 = 16 which is greater than 12.

This is my implementation I am getting TLE and I'm stuck here can't seem to find any way. Please help.

int isAbundant(int n){
int sum = 0;
for (int i=1; i<=sqrt(n); i++){
    if (n%i==0){
        if (n/i == i)
            sum = sum + i;

        else{
            sum = sum + i;
            sum = sum + (n / i);
        }
    }
}
if(sum - n > n) return 1;
else            return 0;
}

int find_abundant_numbers(int n1) {

set<int> s;

if(n1 < 12)  return 0;

for(int i = 12; i <= n1; i++){
    if(i % 2 != 0 && i < 945){
        continue;
    }
    if(s.find(i) == s.end()){
        int isA = isAbundant(i);
        if(isA){
            for(int j = 1; j * i <= n1; j++){
                s.insert(i * j);
            }
        }
    }
    else{
        continue;
    }
    //if(isA) cout << isA << " ";
}

return accumulate(s.begin(), s.end(), 0);
}

Answer 1

Your problem is to find the set of abundant numbers less than n, not to check if one particular number is abundant. Take for instance the sieve of Eratosthenes, an ancient algorithm for finding all prime numbers less than a given number. It doesn't check one by one if a number is a prime, but work more efficiently instead at a higher level, on a range of numbers.

The idea is to have an array std::vector<int> sum(n + 1); (initially all values are set to 0) which is incrementally filled until we obtain the desired sum of strict divisors for all numbers. Given a value (a divisor), the subprocess is to update the array sum by adding this value to all elements in sum representing numbers divisible by it (strictly):

auto propagate_divisor = [&](int divisor) {
    for (int i = 2 * divisor; i <= n; i += divisor)
        sum[i] += divisor;
};

And then, we do that for all possible values:

for (int i = 1; i <= n; ++i)
    propagate_divisor(i);

Now, as sum is built, we just have to pick the abundant numbers (here, I just print them):

 for (int i = 0; i <= n; ++i)
    if (sum[i] > i)
        printf("%i ", i);

You can try it here.