The greatest common divisor (GCD) of two positive integers a and b is the larges
ID: 3753727 • Letter: T
Question
The greatest common divisor (GCD) of two positive integers a and b is the largest integer that divides both a and b. The Euclidean algorithm for finding greatest common divisor, GCD(a, b), is as follows: if b-0, GCD(a,b) is a; otherwise let a b (if this is not true, the values of a and b are simply swapped) and divide a by b to obtain quotient q and remainder r, so that a-qD+r. Then, CD(a, b) GCD(b, r), which means, that the process is continued with b and r replacing a and b. Because the values of remainders decrease in each iteration, a zero remainder will be reached eventually. The last nonzero remainder is the GCD For example: GCD (1260,198) GCD(198,72) GCD (72,54) GCD(54,18) 18. Write a Fortran integer function GCD(a,b) which finds and returns the greatest common divisor of a and b. Write a simple program which reads pairs of integer numbers and uses GCD(a, b) to find the greatest common divisor for each pair until a pair of zeros is entered indicating the end of data.Explanation / Answer
Recursive Function:
//Function Deflection
int GCD(inr a, int b)
{
// this checks whether 'a' is less than 0
if (a<0)
//asign '-a' to 'a'
a=-a;
//this checks whether 'b' is less than 0
if(b<0)
//asign '-b' to 'b'
b=-b;
if (b==0)
return a;
else
return GCD(b,a%b);
}
Program:
Program:
The following program is used to find the GCD of two numbers:
//include required header files
#include
#include
using namespace std:
//function definition
int GCD(int a. int b)
//this checks whether 'a' is less than 0
if (no 0)
//assign '-a' to 'a'
a = -a:
//this checks whether 13 is less than 0
if (b < 0)
//assign '-b' to 'b'
b= -b:
//this checks whether 13' is equal to 0
if (b == 0)
//return 'a'
retum a:
else
//return and call the recursive function
retum GCD(b. a % b):
}
//main function
int main()
{
//call and display the recursive furiction 'GCD()'
cout<< GCD (1260,198);
//pause the screen
system ("pause");
//return 0
return 0;
}
OUTPUT:
sample output:
18
Explanation:
Main function:
Function Definition:
• the function 'GCD()' contains two integer parameters "a " and "b"
o If the above "if condition is true, then assign "-a" to "a".
• The if condition checks whether the variable 'a° is less than 0.
• The next If condition checks whether the variable "b" is less than 0.
o If the above "if condition is true, then assign "-b" to "b".
• The final "if' condition checks whether the variable "b" is equal to O.
o If it is true then, return the variable "a'.
o If the entire 'if condition fats, then it goes to the 'else" part.
• In the "else" part return and call the recursive function "GCD()"
Therefore, the above program displays then
output as 18
Program:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.