Function1: GCD. This function will return the greatest common devisor (GCD)of tw
ID: 3609112 • Letter: F
Question
Function1: GCD. This function will return the greatest common devisor (GCD)of two
integers.In mathematics, GCD is the largest positive integer that dividesboth numbers
withoutremainder. A commonly used algorithm for GCD is Euclideanalgorithm:
Given twonatural numbers a andb: check if bis zero; if yes, a is the gcd. If not,repeat
theprocess using, respectively, b, and theremainder after dividing a byb. The remainder
afterdividing a by bis usually written as a modb.
Theimplementation of this algorithm can be recursively:
gcd(a, b)= a, if b = 0;
gcd(a, b)= gcd(b, a % b), otherwise
There area number of ways to implement them in C/C++. In recursive approach,the
functioncan be
function gcd(a, b)
if b = 0 return a
else return gcd(b, a mod b)
We cancode the above as
intgcd(int a, int b)
{
return ( b== 0 ? a : gcd(b, a % b) );
}
Initerative approach, it can be
function gcd(a, b)
while b 0
t := b
b := amod b
a := t
return a
Theoriginal algorithm is expressed as
function gcd(a, b)
if a = 0 return b
while b 0
if a > b
a := a b
else
b := b a
return a
Inmain( ) function, you need to do the following:
2. readtwo numbers at a time, and output (cout) these two numbers and theGCD of
them, inone single line, with numbers separated by one space
4. createa file called “a4-2.txt”
Example ofa4.txt
43 5
56 4
15 5
90 30
8 2
The outputfor this example would be:
43 5 1
56 4 4
Explanation / Answer
please rate - thanks #include #include int gcd(int a, int b); int main() {int num1,num2; ifstream in; in.open("a4-2.txt"); //open file if(in.fail()) //is it ok? { coutnum1; while(in) {in>> num2; coutRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.