1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euclide's Algorithm to Calculate GCD

  1. Jul 2, 2011 #1
    1. The problem statement, all variables and given/known data
    Using Euclid's algorithm write a program with a function that determines and returns the GCD of two integer arguments.

    This is what i wrote, when i print the remainder is zero, How can i get the last remaninder before the zero value? :confused:

    Thanks

    2. Relevant equations



    3. The attempt at a solution

    [

    #include <iostream>

    using namespace std;
    void remainder ( int, int); //Function Prototype

    int main ()
    {
    int a, b;

    cout << "This Program calculates the GCD of two integers \n"
    << "Please enter two integers" << endl;
    cin >> a >> b;

    remainder (a, b); //Calling the Function


    return 0;

    }

    void remainder ( int a, int b) //Remainder function
    {
    int x, remainder;
    remainder = 0;

    int r;
    if (a > b)
    {r = b;
    r %= b;
    }
    else
    {r = a;
    r %= b;
    }

    cout << r << endl;
    }
    ]
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Jul 3, 2011 #2

    uart

    User Avatar
    Science Advisor

    You need to repeat the process until the remainder is zero and then output the other variable. For example, something like the following code should output gcd(a,b) correctly.

    Code (Text):

    int r;

    if (a > b)
      { r = a;
        a = b;
        b = r
      }


    while (a !=0)
      { r = a;
        a = b % a;
        b = r
      }

    cout << b << endl;
     
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Euclide's Algorithm to Calculate GCD
  1. Algorithm help (Replies: 1)

  2. Greedy Algorithm (Replies: 0)

  3. FindKth algorithm (Replies: 2)

  4. Algorithm Help (Replies: 4)

Loading...