help with Greatest common divisor

[mina1984]

Hi,
im lost and i need help writing a function gcd that returns the greatest common divisor of two integers and has to allow five sets of numbers to be input by the user.
this is what i have so far where i put /* is where i need help the most. if someone could also explain it to me that will also be very well appreciated. thank you in advance

#include <iostream>                              
using std::cout;
using std::cin;
using std::endl;

/* prototype for gcd */

int main()
{
 int a;
 int b;
 
    for(intj=1; j<=5; j++) 
  {
   cout<<"Enter two integers: ";
     cin>>a>>b;
  cout<<" The greatest common divisor of "<< a<<" and"<<b<<" is"
        << /* function call for gcd  */<<"\n\n";
   }

 return 0;
}
/*header for gcd */
{
   int greatest=1;
     for(int i = 2; i <=  ( (x < y) ? x : y); ++i)
  
          if( /* condition to see if both x and y are divisible by i */ )
               greater =1;

         /* statement to return greatest common divisor of both numbers */
}

<< moderator edit: added [code][/code] tags >>

[shre86]

i ll give u a fn or the gcd of 2 nos..

int gcd(int x,int y)
{
   if ( y>x )
      swap(x,y);
   while ( y!=0 )
   {
      temp=y;
      y=x-y;
      x=temp;
      if ( y>x )
         swap(x,y);
   }
   return x;
}

<< moderator edit: added [code][/code] tags and formatting; added missing semicolon >>

just call this fn for the first 2 nos.. then the gcd and the 3rd no. and then there gcd and the 4th no. and so on..
till all the nos are over.. u ll get ur final answer...

[murschech]

The original posting (minah1984) seems to be using the definition of gcd to find the gcd. That's not a bad idea. The one thing missing is that he/she doesn't know how to tell whether i is a common divisor of j and k or not. Here's how to do that: the expression

j%i +  k%i

has the value 0 if i divides both j and k and a positive value otherwise. (I'm assuming i, j, and k are positive).

The response from shre86 is just the euclidian algorithm for the gcd. I can't resist showing you the recursive way to do that.

int gcd(int a, int b)
{    if (b == 0)
          return a;
      return (b, a%b);
}

[Rashakil Fol]

The response from shre86 is just the euclidian algorithm for the gcd. I can't resist showing you the recursive way to do that.

int gcd(int a, int b)
{    if (b == 0)
          return a;
      return gcd(b, a%b);
}

I edited my quote of your code to fix an error ("return gcd(...").

Ironically (and fortunately), this tail-recursive version will just get compiled (by any non-bad compiler) to the non-recursive version, similar to

int gcd(int a, int b)
{
      int tmp;
      while (b) {
            tmp = b;
            b = a % b;
            a = tmp;
      }
      return a;
}

But of course, the recursive drawing of the algorithm is much prettier :-)

[shahid]

i write (GCD) programming code for you in two ways. you check this and compare with your code
First:

// Header files
#include <iostream.h>      
#include<conio.h>   


void GCD(int, int);   // Function prototype


int main()         
{

int first;    //  integer variables first to store first number
int second;   //  integer variables second to store second number
cout<<"Enter two different positive numbers";
cin>>first>>second;  //  getting input from the user two integers through keyboard 

 GCD(first, second);  //calling function GCD and passing two integer values
 getche();  //  get character function getch() used to hold console window
  return 0;
 }  // end main

void GCD(int first, int second)
{

int remainder;  //  integer variables remainder to store remainder.

do { 

    if (first> second)  //  IF condition to check whether the first number is greater than second

         {
           remainder =  first % second; //  if first number is greater than second then dividing first number by second  to get remainder.
            if (!(remainder ==0)) // IF condition to check if remainder Not equal to zero.
             first = remainder;   //  if remainder is not equal to zero then assigning remainder to first
         }
    else                           //Else
           {
             remainder = second % first;  // second number is greater than first then dividing second number by first to get remainder.
              if (!(remainder ==0))  // IF condition to check if remainder Not equal to zero.
               second = remainder;  //  if remainder is not equal to zero then assigning remainder to second number 
           }    

   }while(remainder!=0);  // loop continues untill remainder not equal to zero
    if (first > second) //  IF condition to check whether the first number is greater than second
     {
      cout<<"Greatest Common Diviser  "<< second;  //  if first number is greater than second then displaying second number which is Greatest Common Diviser of two numbers.
     }
    else           //else
      { 
        cout<<"Greatest Common Diviser  "<<first; //   second number is greater than first then displaying first number which is Greatest Common Diviser of two numbers.
      }

} // end GCD

Second Code:

// Header files

#include <iostream.h>         //  header file for input output streams
#include <conio.h>            //  header file for console input output 

 using namespace std;

 //  declares variables

 int GCD (int n1, int n2);

  main()   

      {
      int num1, num2;

      cout << "Enter two differnt positive numbers: ";

      cin >> num1 >>num2;  //  getting input from the user through keyboard

      cout << "Greatest Common Divisor: " 

      << GCD(num1, num2) << endl;   // displaying GCD calculated
      getch();
      }

      int GCD (int n1, int n2)
     {

      int rem;

      while (n2 != 0)

      {
            rem = n1 % n2;

            n1 = n2;

            n2 = rem;
      }

       return (n1);
}

[dark7angelx07]

What would you put in the if condition to see if both x and y are divisible by i ?

[Rashakil Fol]

// Header files
#include <iostream.h>
#include<conio.h>

int first; // integer variables first to store first number
int second; // integer variables second to store second number

int remainder; // integer variables remainder to store remainder.

else //Else

There is such thing as overcommenting, you know :-)

[dark7angelx07]

This is the correct code:

/* prototype for gcd */ = int GCD (int a, int b);

<< /* function call for gcd */<<"\n\n"; = << GCD(a, b) << "\n\n";

/*header for gcd */ = GCD(int x, int y);

All of the above is correct... all we need to figure out is the if statement to determine if both x and y are divisible by i..I could not figure that out...

I tried everything like if(x+y % i) but nothing worked can someone help??

if( /* condition to see if both x and y are divisible by i */ )-->Does anyone know how to do this?????? :o

[Rashakil Fol]

if( /* condition to see if both x and y are divisible by i */ )-->Does anyone know how to do this?????? :o

The number B is divisible by C if the remainder from dividing B by C is zero. The % operator computes the remainder.

[murschech]

This is the correct code:

/* prototype for gcd */ = int GCD (int a, int b);

<< /* function call for gcd */<<"\n\n"; = << GCD(a, b) << "\n\n";

/*header for gcd */ = GCD(int x, int y);

All of the above is correct... all we need to figure out is the if statement to determine if both x and y are divisible by i..I could not figure that out...

I tried everything like if(x+y % i) but nothing worked can someone help??

if( /* condition to see if both x and y are divisible by i */ )-->Does anyone know how to do this?????? :o

I think I've already answered this but I'll do it in more detail.

x is divisible by i if the remainder when x is divided by i is 0, that is, x is divisible by i if and only if x%i == 0. Likewise, y is divisible by i if nd only if y%i== 0. Now the sum of 2 non-negative numbers is 0 if and only if each is 0, so x and y are both divisible by i if and only if x%i+y%i == 0.

[mina1984]

I think I've already answered this but I'll do it in more detail.

x is divisible by i if the remainder when x is divided by i is 0, that is, x is divisible by i if and only if x%i == 0. Likewise, y is divisible by i if nd only if y%i== 0. Now the sum of 2 non-negative numbers is 0 if and only if each is 0, so x and y are both divisible by i if and only if x%i+y%i == 0.

Thank you Murschech
i got it now so its i

if(x%i+y%i==0)
greatest=i

return greatest;

and it works
i made a pretty dumb mistake before instead of the i after greatest i put 1< and everytime it would output 1... it never hurts to check everything again to make sure you wrote it correctly

thanxxxxxxxxxx again murschech and everyone who helped : :mrgreen: