the greatest common divisor

[Cutefriendzoned]

Hey , guys

I think I've solved this , the only problem is the condition , where should the condition " in the gcd function " stop ?
I tried when r!=g but it does not work.

# include<iostream>
#include <string>
using namespace std;
int gcd(int,int);
int main(){
	
	int x,y;
	
	for (int i=1; i!=0; i++){
		cin>>x>>y;
		cout<<"the gcd is: "<<gcd(x,y);
	}
	
	cin.get();
	cin.get();
	return 0;

}
int gcd(int g,int d){
	int r;
	if (g%d==0){
		return d;
	}
	else {
		for (int i=2; i<=??? i++){
			r=g%d;
				g=d;
				d=r;
		
			
		}
		return r;
	}
	
	
}

[keskiverto]

What are you thinking on line 9?

You should not use for-clause on line 25, because the number of iterations is not predictable. while-clause conveys the intent more clearly.

If 0==g%d is good for the first time, why it would not suite the other times too?

[Cutefriendzoned]

forget about the first loop , I could put a negative after finishing the problem.

about the first f , since if it gave us 0 then the gcd is d ,

the problem is how could I find the gcd without the loop on line 25 ??

and I'm sorry I couldn't understand your post , what did you mean " why it would not suite the other times too? "

[Mats]

A quick way to find the gcd would be:

 
int x,y,i; 
std::cin >> x; //You should check these numbers are non-zero integers. 
std::cin >> y; 
if(x % y == 0 && y < x)
{
    return y; 
}
else if(y % x && x < y)//Don't forget the user might not have put them in order highest to lowest!
{
    return x; 
}
else
{
    //Find the highest number. 
    if(x > y)
    {
        for(i = x - 1; i > 0; --i)//Starting with the highest number lower than x... 
       {
             if(x % i == 0) //Is it a divisor of x? 
            {
                   if(y % i == 0) If yes, is it a divisor of y also? 
                   {
                         return i; //If it is a divisor of both, it is the gcd. 
                    }
             }
        }
//And do the same for case y > x... 
}

[keskiverto]

@Mats: That was "interesting" ...

If g is a multiple of d, then d is the answer.
If not, then you compute new g and d.
Now you are back to square one: does new d divide the new g?

I said that 'while' looks better than 'for' in this case. Both are loops.

[Cutefriendzoned]

Thank you @keskiverto ,

but I think you mean do while ? since while and for work the same way ,

but " If g is a multiple of d, then d is the answer. " you mean divides ? , that's why I used the first if to determine it , since if it equals 0 then d would be the gcd,

but I got confused on the else part , I think that I did it right , but since there's no condition to suite the loop , what should I do ?

on the parts or lines " 27-28-29 " I used Euclid's algorithm.

[Mats]

@keskiverto - Did I do something wrong here? *confusion*

[Cutefriendzoned]

# include<iostream>
#include <string>
using namespace std;
int gcd(int,int);
int main(){
	
	int x,y;
	
	for (int i=1; i!=0; i++){
		cin>>x>>y;
		cout<<"the gcd is: "<<gcd(x,y);
	}
	
	cin.get();
	cin.get();
	return 0;

}
int gcd(int g,int d){
	int r,end=1;
	if (g%d==0){
		return d;
	}
	else if (d%g==0){
		return g;
	}
	else {
		for (int i=1; end!=0; i++){
			r=g%d;
				g=d;
				d=r;
				if (g%d==0){
					end=0;
				}
				else {
					r=g%d;
				}
		
			
		}
		return r;
	}
	
	
}

I think that I've got it.

pls guys test this and check , so far every number from my text book " sample output " gave me a correct output.

Still didn't put an if for g or d == 0 , I'll work on it later ^^

[Cutefriendzoned]

I don't think that I need the " else " on the 35 line..