patterncppMinor
Project Euler #12 in C++ - highly divisible triangular number
Viewed 0 times
numberhighlydivisibleprojecteulertriangular
Problem
Project Euler Problem 12 asks (paraphrased):
The nth triangular number Tn = 1 + 2 + … + n. T7 = 28 has 6 divisors (1, 2, 4, 7, 14, 28). What is the first Tn to have over 500 divisors?
After asking for some help on Stack Overflow, I've managed to write this code to solve it:
There're some pieces left that output debugging info to see that everything is working as intended. But overall, it doesn't work as fast as I want it to - or as fast as I expect a proper solution to a Project Euler problem to work.
How can this code be improved? Clearly the program, as it is, now calculates
UPD: After I changed the
The nth triangular number Tn = 1 + 2 + … + n. T7 = 28 has 6 divisors (1, 2, 4, 7, 14, 28). What is the first Tn to have over 500 divisors?
After asking for some help on Stack Overflow, I've managed to write this code to solve it:
#include "stdafx.h"
#include
#include
//#include
#include
int divisors (unsigned int num, std::map& map)
{
int orig_num = num;
for(unsigned int i = 2; i primefactors1, primefactors2;
int no_of_divisors = 1;
divisors(n,primefactors1);
std::cout primefactors_triangle = std::accumulate( primefactors1.begin(), primefactors1.end(), std::map(),
[]( std::map &m, const std::pair &p )
{
return ( m[p.first] +=p.second, m );
} );
primefactors_triangle = std::accumulate( primefactors2.begin(), primefactors2.end(), primefactors_triangle,
[]( std::map &m, const std::pair &p )
{
return ( m[p.first] +=p.second, m );
} );
for ( const auto &p : primefactors_triangle )
{
std::cout << "{ " << p.first << ", " << p.second << " } ";
if (p.first == 2)
no_of_divisors *= p.second;
else
no_of_divisors *= p.second+1;
}
std::cout << std::endl;
return no_of_divisors;
}
int main()
{
int i = 2;
while (overall_factors(i) < 500)
{
std::cout << overall_factors(i) << std::endl;
++i;
}
return 0;
}There're some pieces left that output debugging info to see that everything is working as intended. But overall, it doesn't work as fast as I want it to - or as fast as I expect a proper solution to a Project Euler problem to work.
How can this code be improved? Clearly the program, as it is, now calculates
primefactors for a given number twice. What else is wrong and could be improved? UPD: After I changed the
while loop condition, the problem was solved rather quickly. Still, I believe my code is improvable.Solution
-
This:
can just be a
I'd also recommend using a constant for
If the number isn't significant to the general algorithm, then a comment can be added instead.
-
There is no need for
Although passing the map by reference is okay here, passing it by value (in C++11) will also allow the compiler to decide to perform a move, if desired over a copy.
This:
int i = 2;
while (overall_factors(i) < 500)
{
std::cout << overall_factors(i) << std::endl;
++i;
}can just be a
for-loop:for (int i = 2; overall_factors(i) < 500; ++i)
{
std::cout << overall_factors(i) << std::endl;
}I'd also recommend using a constant for
500 as it is otherwise a magic number. This will make it clear as to what this value represents.If the number isn't significant to the general algorithm, then a comment can be added instead.
-
There is no need for
divisors to just return a 0. It appears it's just modifying the map and displaying it. Also, these are two different things, and a function should just have one role. In this case, it should just modify the map. You should then have a separate void function for displaying the map in the desired format.Although passing the map by reference is okay here, passing it by value (in C++11) will also allow the compiler to decide to perform a move, if desired over a copy.
Code Snippets
int i = 2;
while (overall_factors(i) < 500)
{
std::cout << overall_factors(i) << std::endl;
++i;
}for (int i = 2; overall_factors(i) < 500; ++i)
{
std::cout << overall_factors(i) << std::endl;
}Context
StackExchange Code Review Q#38069, answer score: 4
Revisions (0)
No revisions yet.