CODEWITHSUNDEEP
c++
EpichinoM2
EpichinoM2

Reputation: 137

How to get rid of 2 numbers' common divisors

So I have a function that divides a pair of numbers until they no longer have any common divisors:

void simplify(int &x, int &y){
    for (int i = 2;;++i){
        if (x < i && y < i){
            return;
        }
        while (1){
            if (!(x % i) && !(y % i)){
                x /= i;
                y /= i;
            } else {
                break;
            }
        }
    }
}

How can I make it more efficient? I know one problem in this solution is that it tests for divisibility with compound numbers, when it wouldn't have any of it's factors by the time it gets to them, so it's just wasted calculations. Can I do this without the program knowing a set of primes beforehand/compute them during the function's runtime?

Upvotes: 0

Views: 95

Answers (2)

JVApen
JVApen

Reputation: 11317

Sounds like a job for the C++17 library feature gcd.

#include <numeric>
void simplify(int &x, int &y)
{
    const auto d = std::gcd(x, y);
    x /= d;
    y /= d;
}

Compiler Explorer

Upvotes: 2

Eric Postpischil
Eric Postpischil

Reputation: 222526

Use the Euclidean algorithm1:

  1. Let a be the larger of two given positive integers and b be the smaller.
  2. Let r be the remainder of a divided by b.
  3. If r is zero, we are done, and b is the greatest common divisor.
  4. Otherwise, let a take the value of b, let b take the value of r, and go to step 2.

Once you have the greatest common divisor, you can divide the original two numbers by it, which will yield two numbers with the same ratio but without any common factors greater than one.

Citation

1 Euclid, Elements, book VII, propositions 1 and 2, circa 300 BCE.

Notes

Euclid used subtraction, which has been changed here to remainder.

Once this algorithm is working, you might consider the slightly more intricate Binary GCD, which replaces division (which is slow on some processors) with subtraction and bit operations.

Upvotes: 4

Related Questions