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;
}
{
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 >>

## All 10 Replies

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...

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);
}``````

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 :-)

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);
}
``````

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

#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 :-)

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

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.

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.

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:

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.