Question

The greatest common divisor (GCD) of two values can be computed usingEuclid's algorithm. Starting with the values m and n, we repeatedly applythe formula: n, m = m, ni'.m until m is 0. At that point, n is the GCD ofthe original m and n. Write a program that finds the GCD of two numbersusing this algorithm.

Answer 1

I am writing a C++ program.

#include <iostream> // for input output functions

using namespace std; // to identify objects like cin cout

int gcd(int m, int n) {

//function to compute greatest common divisor of two value m and n

if (n == 0) //if value of n is equal to 0 (base condition)

return m; // returns the value of m

return gcd(n, m % n); }

// calls gcd function recursively until base condition is reached

void get_value(int c, int d){ // function to obtain two values

cout<<"Enter the two values: "<<endl;

//prompts user to enter values of c and d

cin>>c>>d; //reads the input values of c and d

while(c <= 0 || d<= 0){ // the loop continues to ask user to enter positive //values until user enters values greater than 0

cout<<"Enter a positive value";

cin>>c>>d; } //reads values from user

cout<<"GCD of "<< c <<" and "<< d <<" is "<< gcd(c, d); }

//calls gcd funtion to compute greatest common divisor of two values

int main() { // main() function body

int a,b; //two integer variables are declared

get_value(a,b); // calls this method to take values of a and b from user

char ch; // used to enter a choice by user to perform gcd again

while(true) {

//asks the user if he wants to continue to compute gcd

cout<<"Would you like to do another computation or not?(Y/N)\\"<<endl;

cin >> ch; //reads the choice user enters

/*if user enters Y or y then it calls get_value function to take values from user and computer gcd, if user types N or n then the program exits */

if(ch == 'Y'|| ch =='y'){

get_value(a,b);

}else if(ch =='N'||ch =='n'){

break; } }}

Step-by-step explanation:

The program has three methods. gcd method that computes greatest common divisor (GCD) of two values can be computed using Euclid's algorithm. get_value method takes two positive integers from user to find gcd of these values. It keeps asking user to enter positive values until user enters positive values. Third is the main() function which calls get_value function and after computing gcd of two values, asks user to if he wants to find gcd again? If user types Y or y which indicates yes, it moves the program control to get_value function and if user enters n, then the program ends.

Answer 2

The answer is in the explanation and check the attached file for the output

Step-by-step explanation:

GCD.py:

def gcd(a, b):

if b > a:

a, b = b, a

while b != 0:

t = b

b = a % t

a = t

return a

def main():

m = eval(input("Enter m: "))

n = eval(input("Enter n: "))

print("GCD(",m,",",n,") = ",gcd(m,n))

main()

Output: check the output in the attached file