Question

In C language

Please display results

The Euclidean algorithm is a way to find the greatest common divisor of two positive integers, a and b. First let me show the computations for a=210 and b=45.

Divide 210 by 45, and get the result 4 with remainder 30, so 210=4·45+30.

Divide 45 by 30, and get the result 1 with remainder 15, so 45=1·30+15.

Divide 30 by 15, and get the result 2 with remainder 0, so 30=2·15+0.

The greatest common divisor of 210 and 45 is 15.

Formal description of the Euclidean algorithm

Input Two positive integers, a and b.

Output The greatest common divisor, g, of a and b.

Internal computation

1. If a<b, exchange a and b.

2. Divide a by b and get the remainder, r. If r=0, report b as the GCD of a and b.

3. Replace a by b and replace b by r. Return to the previous step.

Your assignment is to write an assembler code (gcd.s) that asks the user two positive numbers and calculates their greatest common denominator.

For example, you program should produce the following outputs:

Enter first positive integer: 6

Enter second positive integer: 8

The GCD is 2

Answer 1

// do comment if any problem arises

//code

#include <stdio.h>

//this function swaps given integers

void swap(int*a,int*b)

{

    int temp=*a;

    *a=*b;

    *b=temp;

}

//this function returns gcd of a and b

int gcd(int a,int b)

{

    if(a<b)

    swap(&a,&b);

    int r=a%b;

    if(r==0)

    return b;

    return gcd(b,r);

}

int main()

{

    int first,second;

    printf("Enter first positive integer: ");

    scanf("%d",&first);

    printf("Enter second positive integer: ");

    scanf("%d",&second);

    printf("The GCD is %d",gcd(first,second));

}

Output: