1) Greatest Common Divisor The greatest common divisor (GCD) of two integers a a
ID: 3757512 • Letter: 1
Question
1) Greatest Common Divisor The greatest common divisor (GCD) of two integers a and b is the largest positive integer that divides both a and b. The Euclidean algorithm for finding this greatest common divisor of a and b is as follows. Assume neither number is 0, and let a be the larger number in absolute value . Divide a by b to obtain the integer quotient q and remainder r such that a-bq r . It is known that GCD(a,b) GCD(b,r), so replace a with b and then b with r, and repeat all the steps until the remainder is 0. Since the remainders are decreasing, eventually a 0 remainder will result. The last nonzero remainder is the greatest common divisor of a and b, i.e., GCDa,b). For example, 1260 198 x 6+72 198 72 x2+54 72-54 x 1+18 54 18 x 3+0 GCD( 1260, 198) = GCD( 198,72) GCD(198,72)GCD(72,54) GCD(72,54) GCD(54,18) GCD54,18) 18 So the GCD of the original two numbers, namely 1260 and 198, is 18. Write a program that includes a user-defined function named GCD that will calculate and return the greatest common divisor of two integer arguments. Do not use the >> 0(Explanation / Answer
#include <iostream>
#include<cstdlib>
using namespace std;
int GCD(int a,int b){
int temp;
//logic
while(b!=0){
temp=a%b;
a=b;
b=temp;
}
return a;
}
int main()
{
int n1, n2;
char c='y';
while(c=='y'){
cout << "Enter two numbers: ";
cin >> n1 >> n2;
n1=gcd(abs(n1),abs(n2));
cout << "Greatest common divisor is " << n1 <<" ";
cout << " Continue? (y/n): ";
cin >> c;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.