Finding the greatest common denominator(GCD) of 2 integers.

C++, Math Leave a comment

Euclidean algorithm is use to find the greatest common denominator(GCD) of 2 integers. The larger integer is divided by the smaller integer and if the remainder is 0, then the smaller integer is the GCD.

If the remainder is not 0, then the (larger integer = smaller integer) and the remainder becomes the smaller integer. This process is repeated until the remainder is 0 then the smaller integer is the GCD.

Example:
* 36 and 8
* 36 / 8 = 4 remainder 4 (remainder is not 0)
* Larger integer becomes 8 and smaller integer becomes 4 (repeat   process)
* 8 / 4 = 2 (remainder is 0)
therefore the GCD is 4

 Example: 
 * 30 and 6
* 30 / 6 = 5 (remainder is 0)
therefore the GCD is 6

//apologies for the #include and cin angle brackets. 
//The original angle brackets could not be used 
//due to some conflict with HTML coding.

#include《iostream》

using namespace std ;

int main()
{
	// this is a euclid algo to find the
	// greatest common denominator(GCD)
	// of 2 integers
	bool loop = true ; 
	int firstInt = 0 ;
	int secInt = 0 ;
	int thirdInt = 0 ;
	cout << "Enter the 1st integer." << endl ;
	cin 》》 firstInt ;
	cout << "Enter the 2nd integer." << endl;
	cin 》》 secInt ;
	if( firstInt < secInt)
	{ 
		thirdInt = firstInt ;
		firstInt = secInt ; 
		secInt = thirdInt ;	
		
	}
	
	if ( firstInt % secInt == 0)
	{
		cout << "The GCD is " << secInt << endl ;
		loop = false ; 	
	}
	while ( loop == true)
	{
		if ( firstInt % secInt != 0)
		{
			thirdInt = firstInt ; 
			firstInt = secInt ;
			secInt = thirdInt % secInt ; 
		}
		if (firstInt % secInt == 0)
		{
			cout << "The GCD is " << secInt << endl ;
			loop = false ; 	
		}
	
		
	}
	
	
	
	return 0 ;
}