Finding the maximum GCD of all pairs
My explorations on GCD and performance

Aside: you might find My blog post interesting, where I found bottlenecks in GCD including branch prediction, lack of instruction parallelism, and the DIV instruction.  Even things like Modulo is significantly slower for signed types compared to unsigned types of the same size!  Since the values being used are all positive, that is another speedup.

For some operations, the opcode is faster for 32-bit than 64-bit; so switching to a smaller version once the numbers get small enough will speed it up.

I found that an algorithm written for computers in 1961 that does no division runs slower than the modern expression when coded naively, but once the bottlenecks in that are found and eliminated, it runs much faster.  The CPU can burn through lots of primitive instructions so the increased length is not significant; it’s the traffic jams inside the CPU that kill the performance.



Your code review

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc.  (See SF.7.)



You should break up the monolithic main into smaller functions.  It is clear that first you read the input, then you do the actual work.

Write the function that does the real work isolated from any real I/O.  It takes parameters and returns values.  You can call that from test cases that means you don’t have to type the input yourself every time!  And you can have a function to read the input in the manner needed, for the final deliverable.

Meanwhile, the functions you write to load arrays from a file like that can be reused for the next problem.  You can be sure it has no code tangled up with the old program — it is just for getting input.

Your code seems complex since GCD itself is just a few lines.  Is that what countGcd is?  The name is odd if it returns GCD, not the count of something.  No, that’s just one step as there is no while loop.  Point is, I have no idea from the names and complete lack of comments just what this code does or how it works.



    for ( size_t j = 0; j &lt; arr.size(); ++j ) {


It appears that this could be a range-based for loop.  I see you refer to arr.at( j ) eight times!  And you are wondering about performance?

for (auto current : array) {


and then I think the long line is the actual GCD calculation because of its name:

    auto GCD= compute_GCD (current, elem);


put that in a separate (readable) function.  It will also make it easy to change the implementation of the GCD algorithm itself without messing with the rest of the program!

        if ( gcd &gt; max_gcd ) {

            max_sum = elem + arr.at( j );
            max_gcd = gcd;
        } else if ( gcd == max_gcd ) {
            size_t sum = elem + arr.at( j );
            if ( sum &gt; max_sum )
                max_sum = sum;
        }    


You want to accumulate the maximum incrementally.  It’s probably not worth using an stl algorithm for that since you are giving it the input incrementally rather than having a prepared list.  It can, however, but split into a separate function or accumulator class.

The complex part here is the tie-breaking.  Understand that the description is simply that of a compound key!  Think of sorting names:  if the last name matches, then sort by the first.

Now std::pair already does this for comparison operators.  So make a pair{GCD,sum} of the current trial, and have the max variable of the same type.  Now you just need a straightforward remember the largest accumulator.

using respair = std::pair&lt;size_t, size_t&gt;;

static respair best { };

void check_for_best (const respair&amp; x)
{
    best = std::max (best,x);
}


basically, it reduces to one line.

max.second will be the max sum.