patterncppModerate
Project Euler 23: Non Abundant Sums
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
There could be other optimizations, but these two seem to be enough.
-
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.