Calculate gcd of two numbers

Question

Following is my code to calculate gcd of two numbers. My intension is not to use any specialised algorithm, just simple maths. Do you see any problem in my solution?

#include <iostream>
#include <algorithm>

int main() {
    int n1, n2;

    std::cin >> n1 >> n2;

    int smaller = min(n1, n2);
    int greater = max(n1, n2);

    if(greater % smaller == 0)
    {
        std::cout << smaller;
        return 0;
    }

    int gcd = 1;

    for (int i = 2; i <= smaller / 2; i++) {
        if(smaller % i == 0 && greater % i == 0)
            gcd = i;
    }

    std::cout << gcd;
    return 0;
} 

Answer 1

While you said that you know about the Euclidean algorithm and "just wanted to implement simple and basic maths principles," I'd like to point out that a basic implementation of the Euclidean algorithm would actually be simpler than what you have. Here's an example:

#include <iostream>
#include <utility>
#include <cstdlib>

int main() {
    int greater, smaller;

    std::cin >> greater >> smaller;

    while (smaller != 0) {
        greater %= smaller;
        std::swap(greater, smaller);
    }

    std::cout << std::abs(greater);
    return 0;
} 

Note that we don't actually need to ensure that abs(greater) >= abs(smaller) before entering the while loop since, if that's not the case, the first iteration of the loop just swaps them.

This GCD implementation has several advantages over yours:

• It's shorter and arguably simpler.
• It correctly handles negative and zero inputs.
• It's also usually faster, especially for large inputs.

Unlike your code, the Euclidean algorithm handles negative inputs correctly. However, the sign of the result will be somewhat arbitrary (and, for C++03 and earlier, implementation-defined), so the code above actually outputs the absolute value of the result. Alternatively, we could simply take the absolute value of the inputs before the loop.

Also, if either input is zero the Euclidean algorithm will output (the absolute value of) the other, which matches the usual definition of the GCD. Your code will typically (if the numbers are non-negative) crash with a division-by-zero error in this case. In the Euclidean algorithm as implemented above, this cannot happen, since the only division is by smaller inside the loop, and the loop condition ensures that smaller cannot be zero.

Ps. One further improvement I'd prefer to make would be to split the GCD calculation into a reusable function, like this:

#include <iostream>
#include <utility>
#include <cstdlib>

int gcd(int greater, int smaller) {
    while (smaller != 0) {
        greater %= smaller;
        std::swap(greater, smaller);
    }
    return std::abs(greater);
}

int main() {
    int n1, n2;
    std::cin >> n1 >> n2;
    std::cout << gcd(n1, n2);
    return 0;
} 

This way, your GCD calculation isn't mixed with your I/O code and other irrelevant "boilerplate". While such mixing may be acceptable for a small single-purpose exercise like this one, for anything more complex you really should try to divide your code as much as possible into independent modules and to maintain a separation of concerns between them. In particular, your math code should not also do I/O, and your I/O code should not do any (nontrivial) math.

Answer 2

1. The code does not account for negative numbers, yet the number type (int) allows them. The program will print 1 for the input -15 10, although 5 is the correct answer.
2. The GCD is usually positive, but your program will print -10 on the input -10 10.
3. A function int gcd(int, int) will make it easier to test and re-use.
4. Since you provided a complete program you probably want to check whether the user actually inputs two numbers and not tree 0.1234 or something else that's not an int.

That being said, thank you for

• not using namespace std;
• properly indenting your code (you could add braces around the if, though)
• using proper names where they were reasonable (n1 and n2 aren't long-lived enough)

I guess that you know that there are better algorithms, so for a simple algorithm like this there is not much to improve. You certainly have to consider negative numbers, though.

Also, some variables are available for the whole scope (n1 and n2), but only used for a short time. Try to limit the scope of a variable as much as possible, as it prevents errors like

for(i = 2; i <= n1 / 2; ++i) // should have been "smaller", whoops

Answer 3

I'll add to comments made by others.

In "real life" - use the standard library version

Well, first and foremost - I understand you're writing this as an exercise, but it must be said that for code you actually intend to use for anything - prefer the C++ standard library's std::gcd from <numeric>.

As a comment kindly points out, this is only available starting from C++17.

Consider recursion over loops

I would suggest you consider avoiding loops in favor of recursion, unless you're working on some super-optimized version (in which case your code would be different anyway).

I'm not claiming that's the "best" thing to do, but in mathematics we often define things recrusively and validate the definition inductively. This also goes for the the gcd: Consider the following recursive implementation (assuming non-negative integers):

constexpr unsigned gcd(unsigned n, unsigned m)
    if (m == 0) { return n; }
    if (n < m)  { return gcd(m, n); }
    return gcd(m, n - m);
}

(I chose unsigned to avoid more code for negative numbers.)

it is very easy to prove this is correct - that each statement is correct. And I do mean prove in the mathematical sense. With imperative code and loops, that doesn't happen as often.

One should note the above implementation is problematic in that it involves much deeper recursion than is necessary: O(n/m) calls (for n > m) rather than O(log(n/m)) (thanks @KevinCline for reminding me to point that out.) Here's another version - more efficient, even more terse, and also recursive:

constexpr int gcd(int greater, int lesser) {
    if (smaller == 0) { return greater; }
    return gcd(m, n % m);
}

... and we don't even need to assume non-negativity.

Consider templating for wider applicability

The last example (as well as many imperative/loop-based versions) could be used for any type which behavies kinda-sorta like the integers (e.g. constitutes a Euclidean Domain if you ignore overflow). So you can implement your GCD at once for all such types:

template <typename EuclideanDomain>
constexpr EuclideanDomain gcd(EuclideanDomain greater, EuclideanDomain lesser) {
    if (smaller == 0) { return greater; }
    return gcd(m, n % m);
}