Member Avatar for qqwushi12345

Solving the greatest common divisor using C++ and the Euclid method

Below is my code:

#include "stdafx.h"
#include "genlib.h"
#include "simpio.h"
#include "math.h"

int _tmain(int argc, _TCHAR* argv[])
{
    int num1,num2,rem;

    printf("Enter 1st number: ");
    num1=GetInteger();
    printf("Enter 2nd number: ");
    num2=GetInteger();
    rem=num1%num2;
    ;if(rem==0)
        {
            printf("The GCD of %d and %d is %d\n",num1,num2,num2);
        }
     else
        {num1=num2;
         num2=rem;
         while (1==1)
         {
             if (rem==0)
                 {
                     printf("The GCD of %d and %d is %d\n",num1,num2,num2);
                 }
             else
                 {
                     num1=num2;
                     num2=rem;
                 }
          }
         }  
}

Please tell me what I did wrong, because the above code doesn't work for all numbers.

thank you

Edited by mike_2000_17 because: Fixed formatting
  • 3 Contributors
  • 2 Replies
  • 203 Views
  • 21 Hours Discussion Span
  • Latest Post Latest Post by daviddoria

Dani AI

Generated

Quick diagnosis: there are two root problems. As noted, while (1==1) creates an infinite loop; more importantly, rem is computed once before the loop and never updated inside it, so the loop never makes progress. There’s also no guard against num2 == 0 (division by zero) and printing inside the loop uses the wrong variable once you shift num1/num2. Handle negatives and the special case GCD(0,0).

Euclid’s method (iterative) is simply:
repeat r = a % b, then a = b, b = r, until b == 0. The GCD is abs(a). Example trace: GCD(48,18) -> 48%18 = 12 -> 18%12 = 6 -> 12%6 = 0 -> gcd = 6.

A compact, robust C++ approach (replace input if you want to keep GetInteger()):

#include <iostream>

long long gcd(long long a, long long b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    long long x, y;
    std::cout << "Enter 1st number: "; if (!(std::cin >> x)) return 0;
    std::cout << "Enter 2nd number: "; if (!(std::cin >> y)) return 0;
    if (x == 0 && y == 0) { std::cout << "GCD(0,0) is undefined\n"; return 0; }
    std::cout << "GCD is " << gcd(x,y) << '\n';
}

Troubleshooting tips: test with (48,18), (18,48), (7,3), (0,5), and (0,0). If you keep the original library calls, ensure you recompute rem each loop iteration and use while (num2 != 0) and print num1 when the loop finishes. As asked, those tests will show which inputs caused the original code to hang. If using C++17 or later, std::gcd in <numeric> is a standard alternative.

Recommended Answers

All 2 Replies

Member Avatar for Weichen

Your while() condition in the first else statement is (1==1) which is always true.
It might be why you are having the problem.

Member Avatar for daviddoria

Please use code tags when posting code. Also, which numbers are not working correctly? You should be as detailed as possible when posting your problems so people here can help you as efficiently as possible.

David

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.