HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppModerate

Project Euler 23: Non Abundant Sums

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
nonprojectabundanteulersums

Problem

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 
#include 

//Calculates divisors
void Divisors(unsigned number, std::vector &result){
    for(unsigned a = 1; a  divisors;
    Divisors(number, divisors);
    for(unsigned a = 0; a  number){
        return true;
    }
    else{
        return false;
    }
}
//pushes back abundant numbers
void Abundant(unsigned limit, std::vector &abunNumbers){
    for(unsigned a = 1; a  const& abunNumbers, std::vector &sumAbun){
    for(unsigned a = 0; a abunNumbers;
    Abundant(limit, abunNumbers);

    std::vectorsumAbun(limit,false);
    SumOfAbundant(limit, abunNumbers, sumAbun);

    for(unsigned a = 0 ; a < sumAbun.size() ; a++){
        if(!sumAbun[a]){
        result += a;
        }
    }
    std::cout << result;
}

Solution

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.

Context

StackExchange Code Review Q#48016, answer score: 11

Revisions (0)

No revisions yet.