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

Project Euler #12 in C++ - highly divisible triangular number

Submitted by: @import:stackexchange-codereview··
0
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:

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

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.