3
\$\begingroup\$

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 <iostream>
#include <map>
//#include <algorithm>
#include <numeric>

int divisors (unsigned int num, std::map<int, int>& map) 
{
    int orig_num = num;
    for(unsigned int i = 2; i <= num; ++i)
    {
        while (num % i == 0) 
        {
            num /= i;
            ++map[i];
            //std::cout << map[i] << "\t";
        }
    }
    std::cout << orig_num << " = "; 
    for(auto& iter:map)
        std::cout << iter.first <<  "^" << iter.second << " * ";
    return 0;
}

int overall_factors(unsigned int n)
{
    std::map <int, int> primefactors1, primefactors2; 
    int no_of_divisors = 1;
    divisors(n,primefactors1);
    std::cout << std::endl;
    divisors(n+1,primefactors2);
    std::cout << std::endl;
    std::map<int, int> primefactors_triangle = std::accumulate( primefactors1.begin(), primefactors1.end(), std::map<int, int>(),
        []( std::map<int, int> &m, const std::pair<const int, int> &p )
    {
        return ( m[p.first] +=p.second, m );
    } );

    primefactors_triangle = std::accumulate( primefactors2.begin(), primefactors2.end(), primefactors_triangle,
        []( std::map<int, int> &m, const std::pair<const int, int> &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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Optimization hints (Implementation in Python takes around 50ms) \$\endgroup\$
    – jfs
    Dec 26 '13 at 17:02
4
\$\begingroup\$
  • 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.

\$\endgroup\$
9
  • \$\begingroup\$ Thanks. Could I just add a really clear comment about the intent behind 500 instead of using a constant for it? \$\endgroup\$
    – Chiffa
    Dec 25 '13 at 17:01
  • \$\begingroup\$ You may, especially if the number is not that significant to the algorithm. \$\endgroup\$
    – Jamal
    Dec 25 '13 at 17:03
  • \$\begingroup\$ originally the code had a commented link to the original project euler page about the problem (it's still in the code on my PC), therefore I expected anyone who'd read the code to read the problem statement & have a clear idea about the meaning of 500. \$\endgroup\$
    – Chiffa
    Dec 25 '13 at 17:05
  • \$\begingroup\$ I primarily meant that in general, as it's preferable to use as few magic numbers as possible. Not every such number needs a constant, just ones with a meaning behind them. \$\endgroup\$
    – Jamal
    Dec 25 '13 at 17:09
  • \$\begingroup\$ Got it, will try to follow yor advice. \$\endgroup\$
    – Chiffa
    Dec 25 '13 at 17:13
3
\$\begingroup\$

One thing you can do immediately to cut your running time by a large factor is to modify your main function:

int main() {
    int num_factors = 0;
    for (int i = 2; num_factors < 500; ++i) {
        num_factors = overall_factors(i);
        std::cout << num_factors << "\n";
    }
}

Two things:

  1. I only compute overall_factors(i) once instead of twice for each value of i.
  2. I output "\n", not std::endl, to end the line. std::endl not only outputs a line break, it flushes std::cout. Flushing output buffers is slow.

Likewise, convert your std::cout << std::endl elsewhere into std::cout << "\n" (or remove in-function input entirely) and you'll see a marked speed improvement. The buffer will automatically flush from time to time; if you want to see more frequent flushing, you can add this to your main loop:

if (!(i % 10)) std::cout << std::flush;

As to the rest of your code, it is somewhat difficult to review. Your functions and their parameters have uninformative names (e.g. map is not a good name for a map you're passing; primefactorization would be better in that case). Your lambdas confusingly return a statement of the form return (foo(), bar());; it is misleading to use the comma operator like that -- this isn't Python, your lambdas are allowed multiple statements!

Why do you use accumulate at all? You can just pass the same map to both calls of divisors and get the same result as accumulating the two.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for explaining the flushing issue. Also, I used accumulate to see how to - in other words, as an exercise. So I agree that there's a possibly better solution without it. \$\endgroup\$
    – Chiffa
    Dec 26 '13 at 23:11
2
\$\begingroup\$

At a quick first-glance, one thing you can do that should cut run-time quite a bit is to change that STL map of ints to ints to an array of ints. I'm not sure how big your keys get, but even for some pretty large sizes this should be much quicker, but perhaps less elegant. In general STL maps have a reputation for being somewhat slow, so if you can eliminate your dependency on this data structure (a red-black tree) somehow, things should speed up.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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