Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Here is my solution to Project Euler 23: Non Abundant Sums. I know I'm doing the Divisors function brute force, but I can't seem to get it to work any other way. Any improvements are welcome.

#include <iostream>
#include <vector>

//Calculates divisors
void Divisors(unsigned number, std::vector<unsigned> &result){
    for(unsigned a = 1; a < number; a++){
        if(number % a == 0){
            result.push_back(a);
        }
    }
}
//Calls for divisors and adds them
unsigned SumOfDivisors(unsigned number){
    unsigned result = 0;
    std::vector<unsigned> divisors;
    Divisors(number, divisors);
    for(unsigned a = 0; a < divisors.size(); a++){
        if(divisors[a] < number)
            result += divisors[a];
    }
    return result;
}
//Calls calculates the sum of divisors to see if it is Abundant
bool IsAbundant(unsigned number){
    if(SumOfDivisors(number)> number){
        return true;
    }
    else{
        return false;
    }
}
//pushes back abundant numbers
void Abundant(unsigned limit, std::vector<unsigned> &abunNumbers){
    for(unsigned a = 1; a < limit; a++){
        if(IsAbundant(a)){
            abunNumbers.push_back(a);
        }
    }
}

//Find's all number's that are the sum of two abundant numbers
void SumOfAbundant(unsigned limit, std::vector<unsigned> const& abunNumbers, std::vector<bool> &sumAbun){
    for(unsigned a = 0; a < abunNumbers.size(); a++){
        for(unsigned b = a; b < abunNumbers.size(); b++){
            if(abunNumbers[a]+abunNumbers[b] <= limit){
                sumAbun[abunNumbers[a]+abunNumbers[b]] = true;
            }
        else{
            break;
        }
        }
    }
}

int main(){
    const unsigned limit = 28123;
    unsigned result = 0;

    std::vector<unsigned>abunNumbers;
    Abundant(limit, abunNumbers);

    std::vector<bool>sumAbun(limit,false);
    SumOfAbundant(limit, abunNumbers, sumAbun);


    for(unsigned a = 0 ; a < sumAbun.size() ; a++){
        if(!sumAbun[a]){
        result += a;
        }
    }
    std::cout << result;
}
share|improve this question
    
Clean and well structured code, but your Divisors code populates a vector that is thrown away by SumOfDivisors. Combining those, retaining only the sum would eliminate the divisors vector completely and save a small amount of time. The biggest gains will be algorithm changes, though. –  Edward Apr 24 at 3:04
    
@Edward: Eliminating the vector would actually be a huge percentage of the time. I will bet more than 50%. Yes, an algorithmic change would be even better. But so what, it's already got to be under 1 second. –  Dov Apr 24 at 4:20
    
if you look at the wikipedia page for abundant numbers, it states that the largest number that can't be made by summing two abundant numbers is 20161. 28123 and above is only the smallest number that can be proven. that may cut down your time a little –  birthofearth Apr 24 at 6:31

3 Answers 3

up vote 10 down vote accepted

I would recommend the following changes:

  • Math is your friend. Factorize the number into prime powers (a precalculated table of primes is of immence value for a lot of Project Euler problems), and use a formula from this article.

  • Memoize. As soon as you identify a single (prime) divisor of a number, and take the quotient, notice that the quotient was already inspected and factorized. A vector of tuples (prime, power) representing a factorization may also help a lot.

There could be other optimizations, but these two seem to be enough.

share|improve this answer

I was perplexed why you want a better answer if your current answer is able to solve this in seconds, but if you are interested in the math, there are definitely better ways to do it. They just don't matter much if the maximum number is on the order of 28000.

If you eliminate the lists and go up to the square root, the code should get faster by a factor of 1000 or so, a rough estimate based on the difference between 28000 and the square root which is 167. Another factor of 2 due to only dividing by odd numbers after checking 2.

But if you look at Wikipedia on abundant numbers: http://en.wikipedia.org/wiki/Abundant_number You will see that the first abundant number that is not divisible by 2 is 5391411025 First of all, that's way more than 28000. So you can immediately ignore any number that is not even in your search for abundant numbers. Wikipedia says 2 or 3, which is confusing and seems wrong. Perhaps I misunderstood them but I was looking at their list of abundant numbers, and 20 is abundant, and it's not a multiple of 3 (it's a multiple of 5). 1+2+4+5+10 > 20

Still, this means that any number that is abundant is going to be divisible by 2 and either 3 or 5 (or both). Think of it. How are you going to get factors that sum to a lot? You need factors that are an appreciable fraction of the whole number. The closest you can get to n is n / 2. The next closest is n / 3.

The highest number you have to check is the square root, and since the square root of 28000 is about 170, that's the high end. But you can immediately terminate if you find that the number is already abundant, or if the sum is so low that it cannot possibly become abundant. So try only even numbers, and do the following:

int factors = 1 + 2 + n / 2;
if (n % 3 == 0)
  factors += 3 + n/3 + 6 + n / 6;
if (n % 5 == 0)
  factors += 5 + n / 5;
if (factors > n)
  abundant.push_back(n);

Even if I'm not quite right, 99.9% of the abundant numbers will immediately be abundant with this test, so in constant time you will have detected them. You could check a few manually the rest of the way if you are "close" to abundant. I leave you to decide how close is close.

A number that is not divisible by 2,3,4,5,6,7 is almost certainly not abundant. So you can find that critical value and then not test anything higher. Store the abundant numbers into a vector.

Given the list of abundant numbers:

for (i = 0; i < abundant.size(); i++)
  for (int j = i+1; j < abundant.size(); j++) {
    int abundantSum = abundant[i] + abundant[j];
    if (abundantSum < 28123)
      numbers[abundantSum] = true;
  }
}
share|improve this answer

The problem states that all numbers greater than 28123 are out, so you only need to consider numbers up to that limit. That's not a lot of numbers.

Having said that, each project Euler problem involves a new math skill. I'll provide some optimization hints.

In this case, the math you need is factorization. You are dividing by every number from 1 to n-1 in order to factorize n. You don't have to do that.

  1. All numbers are divisible by 1, so don't even test it. You can start your count at 1 instead of zero.

  2. You are summing up the factors, so don't build a list, build a running total. That will reduce a lot of inefficiency. In fact, you overuse lists in several places: not only are you building a list of factors, but you are building a list of the numbers you want. Nothing in this problem said you had to build a list of anything, just sum the numbers you find. Granted, the only one that really affects the timing is the list of factors.

  3. You only need to go up to the square root of a number to factor. Consider 28: divide by 1, get 28 (which by the way doesn't count). Divide by 2, get 14. Divide by 4, get 7. You don't have to divide by 7, because you already got it by dividing by 4. That cuts the problem to \$O(\sqrt{n})\$ rather than \$O(n)\$.

The suggestion above is still a brute-force approach, but it's a more efficient brute-force solution.

share|improve this answer
2  
Actually on my quad-core machine running 3.2GHz, this code takes over 8 seconds. –  Edward Apr 24 at 12:37
1  
As evidenced by downvotes, the condescension in your original answer is disfavoured by the Code Review community. I've edited it to have a neutral tone. Remember, even expert programmers were once beginners too. You obviously have a lot of knowledge to contribute, but please remember to be nice. –  200_success Apr 25 at 18:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.